[알고리즘] 재귀함수 활용 피보나치 수열

재귀는 자기 자신을 재 참조하는 방법을 말한다. 재귀 호출(Recursive call)의 형태로 많이 사용 한다.

재귀함수란 함수안에서 자신을 다시 호출하여 작업을 수행하는 방식을 의미한다.

 

예시:

def recursive_call():
    print("Recursive call")
    recursive_call()

recursive_call()

위의 코드를 보면 recursive_call 함수 안에서 다시 recursive_call 함수를 호출 하고 있는 걸 볼 수 있다.

 

실행을 하면 print문을 실행 후 아래 사진과 같은 에러가 발행하는데요, 왜냐하면 Python에서 maximum recursion depth 의 최대값이 1000으로 정해져 있어서 에러가 발생한 것이다.

recursive_call함수를 호출하다가 maximum recursion depth를 초과하면 RecursionError이 발생하게 된다.

그래서 재귀 함수를 사용 시 함수 종료 조건을 넣어 maximum recursion depth을 초과하지 않게 하는 것이 좋다.

 

재귀함수를 사용한 쉬운 알고리즘 예시로는 피보나치 수열이 있다.

피보나치 수열은 첫 번째, 두 번째항이 1 이고, 세 번째 항 부터는 바로 앞의 두 항의 합으로 정의된 수열이다.

세 번째항은 첫 번째항 1과 두 번째 항 1을 더한 2 이며, 네 번째 항은 두 번째 항1과 세 번째 항 2을 더한  3인 것이다.

 

def fib(n):
    
    if n < 3:
        return 1
    else:
        return fib(n-1) + fib(n-2)

fib(4)

코드를 보면 첫 번째 항과 두 번째항은 어차피 1 이기 때문에  3이하면 바로 1을 return한다.

 

fib(4) = fib(3) + fib(2) 

fib(3) = fib(2) + fib(1)

fib(2) = 1

fib(1) = 1

 

fib(4) =    2     +    1     = 3

fib(3) =    1     +    1     = 2 

fib(2) = 1

fib(1) = 1