재귀함수 Recursion Funtion

DFS와 BFS를 구현하려면 재귀 함수도 이해하고 있어야 한다.

 

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미 합니다.

 

재귀함수 (recursion)

• 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 부른다.
• 반드시 탈출조건이 있어야 stack overflow를 방지할 수 있다.
• 같은 행위가 반복될 때 재귀함수를 사용한다.

 

예시 1  - Factorial

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)
        
factorial(5)  # 120

 

 

예시 2  - 순차탐색

def search(array, begin, end, target):
    if begin > end:
        return -1
    elif target == array[begin]:
        return begin
    else:
        return search(array, begin + 1, end, target)


array = [1, 3, 5, 7, 9, 11]
target = 7
search(array, 0, 5, target)  # target의 index는 3

 

 

예시 3  - 2진수 변환

def binary(n):
    if n < 2:
        print(n, end='')
    else:
        binary(n // 2)
        print(n % 2, end='')


binary(10)  #1010

 

 

예시 4  - 0~n 까지의 합계 구하기

def sum(n): 
    if n == 0:  # n=0 이면 합은 0이다
        return 0
    return n + sum(n - 1)  # n이 0보다 크면 0에서 n 까지의 합은, n-1까지의 합에 n을 더한 것이다.


sum(10)  # 55

 

 

예시 5  - x의 n 제곱 구하기

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n-1)

power(2,10) # 1024

 

 

예시 6  - 피보나치수열

# 피보나치 수열의 index n의 값을 리턴
def fibo(n):
    # 재귀함수는 탈출조건이 꼭 필요하다.
    if n == 0 or n == 1:
        return 1
    return fibo(n - 2) + fibo(n - 1)


# index n까지의 피보나치 수열 구하기
def fibo_list(n):
    fibo_arr = []
    
    for i in range(n):
        fibo_arr.append(fibo(i))
    return fibo_arr


fibo_list(8)  # [1, 1, 2, 3, 5, 8, 13, 21]
fibo(3)  # 3

 

 

예시 7  - 최대공약수

def gcd(m, n):
    if m < n:
        m, n = n, m
    if m % n == 0:
        return n
    else:
        return gcd(n, m % n)


print(gcd(48, 8))  # 8