혼자 공부하는 파이썬 개정판 58강 - 재귀 함수(2): 피보나치 수열

피보나치 수열의 정의와 재귀 구현

피보나치 수열은 첫 번째와 두 번째 항이 1이고, 세 번째 항부터는 앞 두 항을 더한 값으로 이어지는 수열이에요. 예를 들어 3번째는 1+1=2, 4번째는 2+1=3, 5번째는 3+2=5가 되죠. 이 규칙을 재귀 함수로 그대로 옮기면 됩니다.

함수를 만들 때는 n이 1이거나 2일 때 1을 반환하고, 그 외에는 f(n-1) + f(n-2)를 반환하는 구조예요. 아래처럼 if-elif로 조건을 연결하면 완성됩니다.

```python def f(n): if n == 1: return 1 if n == 2: return 1 return f(n-1) + f(n-2)

print(f(3), f(4), f(5)) # 2 3 5 ```

이 코드를 실행하면 바로 2 3 5가 출력돼요. 재귀 호출이 두 번 일어나는 구조라서 작은 n에서는 문제없이 동작하죠. 다만 n이 커질수록 호출 횟수가 기하급수적으로 늘어나는 점을 미리 알아두는 게 좋아요.

실행 흐름 분석과 성능 저하 원인

f(5)를 구할 때 실제 호출 순서를 따라가 보면 f(4)와 f(3)이 먼저 필요하고, f(4)는 다시 f(3)과 f(2)를 부릅니다. f(3)도 f(2)와 f(1)를 호출하죠. 이렇게 한 번 호출할 때마다 두 갈래로 나뉘는 트리 구조가 만들어져요.

문제는 같은 값을 여러 번 계산한다는 점입니다. f(8)을 구하는 과정에서 f(7)이 세 번, f(6)이 다섯 번 이상 중복 호출돼요. n=10만 되어도 수십 번, n=35에서는 수만 번 이상 같은 계산이 반복됩니다. 실제로 repl.it에서 f(35)를 돌리면 15초 정도, f(50)는 2시간 이상 걸리는 이유가 바로 이 중복 때문이에요.

그래프 이론을 배우면 이 실행 흐름을 트리 순회로 쉽게 분석할 수 있지만, 지금 단계에서는 “같은 계산을 반복한다”는 점만 기억해도 충분합니다.

메모화를 활용한 속도 개선

한 번 계산한 결과를 딕셔너리에 저장해 두고, 다음에 같은 n이 나오면 바로 꺼내 쓰는 방법을 메모화라고 해요. 아래 코드처럼 memo 딕셔너리를 추가하면 됩니다.

```python memo = {}

def f(n): if n in memo: return memo[n] if n == 1: val = 1 elif n == 2: val = 1 else: val = f(n-1) + f(n-2) memo[n] = val return val

print(f(50)) # 순식간에 결과 출력 ```

이제 f(50)도 1초 이내에 끝나요. memo에 1과 2를 미리 넣어 두면 if문을 더 줄일 수도 있습니다. 파이썬 3.8 이상에서는 walrus 연산자(:=)로 더 짧게 쓸 수 있지만, repl.it 환경에서는 위 형태가 가장 안전해요.

실전에서는 n이 1000 이상이어도 메모화만 제대로 하면 빠르게 구할 수 있으니, 재귀 함수를 쓸 때 항상 메모화를 고려해보세요.