[AL]피보나치 수열

재귀로 쉽게 풀 수 있는 문제. 그렇지만 재귀 깊이를 생각해야

피보나치 수열은 이미 많은 문제에서 구현이 되어있다.

필자도 모 강의에서 피보나치 수열을 재귀를 통하여 풀어보았던 경험이 존재하기에 프로그래머스 피보나치 수열 문제를 당연하게도 재귀를 통해 넣었다.

def solution(n):
    answer = fib(n)
    return answer
    
    
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return ((fib(n-1) % 1234567) + (fib(n-2) % 1234567))

그런데 테스트케이스 7부터 주루륵 틀리는 것이 아닌가?

무엇이 문제일까 찾아보다가 질문방에서 재귀 깊이 오류가 존재한다고 하였다.

재귀의 호출이 너무 깊으면 반복문보다 느린 성능을 보여준다고 한다.

간결하지만 성능이 더 안나올 수도 있는 재귀문을 버리고 반복문으로 다시 피보나치 수열을 짰다.

def solution(n):
    
    fib = []
    fib.append(0)
    fib.append(1)
    
    for i in range(2,n+1):
        fib.append( (fib[i-1]% 1234567) + (fib[i-2]% 1234567))
        
        fib[i] = fib[i] % 1234567 
    
    answer = fib[-1]
    return answer

그랬더니 모든 테스트 케이스가 통과되었다.