[Python] 재귀 함수를 통한 피보나치 수열 구현해보기

재귀함수

재귀함수는 자기자신을 호출하는 함수란 뜻으로 많이 쓰이는 알고리즘이다.

일반적으로 반복되는 코드를 작성할때 반복문을 사용하지만 재귀함수를 사용하게되면
반복문을 사용할 때 보다 더 클린한 코드를 작성할 수 있다는 장점이 있지만
반복문보다 느리고 스택 오버 플로우가 발생할 수 있다는 단점도 있다.

피보나치 수열

피보나치 수열 : 1 1 2 3 5 8 13 ....
규칙 : a1 = 1 ,a2 = 1 ,an= (n-1) + (n-2)

문제 정의 : an= (n-1) + (n-2)
종료 시점 : a1 = 1

피보나치 수열 < 첫번째 시도 >

def fibonacci(n):
    if  n==1:                    
        return 1         
    else:
        return fibonacci(n-1) + fibonacci(n-2)    

value = int(input())

count = value
for i in range (0,value):
    print(fibonacci(count))
    count -= 1

첫번째 시도 Error

RecursionError: maximum recursion depth exceeded in comparison

재귀와 관련된 에러이며 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때 발생한다.

Error 에 대한 나의 생각

재귀의 깊이가 깊다는 뜻은 무한 루프에 빠진다는 것과 비슷하게 느껴진다.
종료시점에서 오류가 발생했다는 의심과 함께 종료해주는 구문을 수정할 필요성이 있어보인다.
규칙이 정해지지 않은 수열 첫번째와 두번째을 모두 조건식에 넣어주고 논리 연산자 or을 사용하여 f(1),f(2)
일때 1을 리턴해주면 될 것 같다.

피보나치 수열 < 두번째 시도 >

def fibonacci(n):
    if n==1 or n==2 :      #수정한 부분
        return 1           
    else:
        return fibonacci(n-1) + fibonacci(n-2)    

value = int(input())

count = value
for i in range (0,value):
    print(fibonacci(count))
    count -= 1

complete

성공에 대한 나의 생각

재귀함수는 컬스택-호출 하는 흐름을 이해하는 것이 너무 어렵다...
코드가 짧아보이지만 파이썬 튜터로 실행하면서 하나하나 뜯어보면서 이해하려고 하니 과정도 길고
복잡했다. 그 뿐만아니라 피보나치 수열에서 수열의 규칙보다 종료시점을 조건을 거는 구문에 생각하는 데에 오래 걸렸다