📍문제

[프로그래머스] Lv.2 피보나치 수
이 문제를 올리는 이유는 코드 짜는 거 자체는 어렵지 않았지만, 재귀함수의 시간초과에 대해서 정리해두고 싶어서 문제풀이를 올리기로 하였다.

📍풀이

• 재귀함수를 이용해서 풀면 시간초과가 나는 문제이다.
• 재귀함수를 이용하지않고 반복문을 이용해 fibo배열을 생성 후 계산해준다.

💻첫번째 코드(재귀함수 사용, 시간초과)

def fibo(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return fibo(n-1)%1234567 + fibo(n-2)%1234567
                           
def solution(n):
    return fibo(n)

보통 피보나치수열을 파이썬으로 구현하라하면 재귀함수를 이용하는 경우가 많다. 따라서 재귀함수로 구현하였는데, 이러면 테스트 7부터 런타임 에러와 시간초과가 뜬다.

💻두번째 코드(통과)

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

단순하게 반복문을 이용하여 배열에 피보나치 수들을 저장해 준 다음 맨 마지막 원소를 1234567로 나눈 나머지를 return해주면 된다.

재귀함수 시간초과

재귀적 함수 호출은 코드를 유연하게 짜는데 도움을 주지만 비효율적인 경우도 존재하는데, 대표적인 예가 피보나치 수열(Fibonacci sequence) 이다.
피보나치 수열의 경우 모든 경우를 탐색하기 때문에 시간이 오래걸릴 수 밖에 없는 것.. 이전에 계산했던 값에 대해서 다시 계산하기 때문에 자원 낭비가 크다.
n이 증가하면 시간 복잡도 O(2n)도 가파르게 증가한다.

파이썬은 재귀함수를 이용하면 끝없이 자신을 호출함으로써 스택 오버플로를 발생시키는 것을 막기 위해 재귀깊이(recursion depth)를 설정해 두었다.

코드를 직관적으로 이해하기에는 재귀함수가 효과적이지만 효율적인 코드를 작성하려면 다른 방법도 많이 고려해봐야 할 것이다!!