11 — 재귀 실습 (피보나치)

람다가 1,1,2,3,5,8 수열을 보며 "앞 두 개를 더하네?"라고 규칙을 발견하고, 제네릭이 토끼 그림으로 거들자 돌핀쌤이 "그게 바로 피보나치예요. 지난 시간에 배운 재귀로 만들 수 있어요"라고 이어 주는 도입

🙋‍♀️ 람다: "선생님, 이 숫자 카드 좀 보세요. 1, 1, 2, 3, 5, 8... 앞 두 개를 더하면 다음 수가 나와요!"

🐬 돌핀쌤: "두 친구가 오늘 배울 걸 미리 찾아냈네요! 그게 바로 피보나치 수열이에요. 그리고 이 규칙은 지난 시간에 배운 재귀로 아주 자연스럽게 만들 수 있답니다."

🎯 오늘 완성할 코드는?

오늘 만들 건 재귀로 피보나치 수열 구하기예요. n번째 피보나치 수를 돌려주는 짧은 함수랍니다.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

def fib(n):
    if n <= 2:                       # base case (종료 조건)
        return 1
    return fib(n - 1) + fib(n - 2)   # 앞 두 수를 더함

print(fib(1))   # 1
print(fib(2))   # 1
print(fib(5))   # 5
print(fib(10))  # 55

실행하면 이렇게 나와요.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 에서 5번째는 5, 10번째는 55가 맞죠?

🐬 돌핀쌤: "단 4줄짜리 함수예요. 그런데 이 함수가 자기 자신을 두 번 부르고 있어요. 이게 오늘의 핵심이에요. 지금부터 이 코드가 왜 피보나치를 구해내는지 한 줄씩 풀어볼게요."

💡 어떻게 풀까? — 앞 두 수를 더하기

피보나치 수열은 람다가 발견한 그대로, 앞의 두 수를 더해서 다음 수를 만드는 수열이에요.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
        ↑
   1 + 1 = 2,  1 + 2 = 3,  2 + 3 = 5 ...

제네릭이 떠올린 토끼 이야기로 보면 더 쉬워요. 피보나치는 원래 토끼가 새끼 치는 문제에서 나왔거든요.

이달의 쌍 수 = 저번 달 쌍 수 + 그 전 달 쌍 수

이걸 식으로 쓰면 이래요.

fib(1) = 1            ← 더 이상 쪼갤 수 없는 시작값
fib(2) = 1            ← 더 이상 쪼갤 수 없는 시작값
fib(n) = fib(n-1) + fib(n-2)   ← 나보다 작은 두 문제를 풀어서 더함

🙋‍♂️ 제네릭: "큰 문제(fib(n))를 더 작은 문제 두 개로 쪼개네요. 이게 지난 시간에 배운 재귀구나!"

이 식이 그대로 맨 위 코드가 돼요. 식의 fib(n-1) + fib(n-2) 가 코드의 return fib(n - 1) + fib(n - 2) 와 똑같죠?

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 멈출 곳을 정해요 — base case

    if n <= 2:        # base case (종료 조건)
        return 1

재귀는 언젠가 멈춰야 해요. 멈추는 가장 작은 값을 base case(종료 조건) 라고 불러요. 피보나치는 fib(1) 과 fib(2) 가 둘 다 1이라서, n 이 2 이하면 더 쪼개지 않고 바로 1 을 돌려줘요.

💡 만약 이 줄이 없으면 fib 는 fib(0), fib(-1), fib(-2)... 끝없이 내려가다가 멈추지 못해요. base case는 재귀의 브레이크예요.

② 나를 두 번 불러요 — 재귀 호출

    return fib(n - 1) + fib(n - 2)   # 앞 두 수를 더함

n 이 2보다 크면, 자기 자신을 두 번 불러서 그 결과를 더해요. 지난 시간에 배운 재귀는 자기 자신을 한 번 불렀는데, 피보나치는 식 그대로 fib(n-1) 과 fib(n-2) 두 번 불러요.

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

③ 전체가 어떻게 굴러가는지 — fib(5) 호출 트리

람다가 물었어요. "두 번씩 부르면 안에서 무슨 일이 일어나요?" fib(5) 가 실제로 어떤 함수를 부르는지 호출 트리로 그려 볼게요.

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) → 1
│   │   └── fib(1) → 1      (fib(3) = 1 + 1 = 2)
│   └── fib(2) → 1          (fib(4) = 2 + 1 = 3)
└── fib(3)                  ← 위에서 계산했는데 또 계산!
    ├── fib(2) → 1
    └── fib(1) → 1          (fib(3) = 1 + 1 = 2)
                            (fib(5) = 3 + 2 = 5)

맨 아래(fib(1), fib(2))에 닿으면 1 을 돌려주고, 그 1들을 위로 차곡차곡 더해 올라가서 마지막에 fib(5) = 5 가 돼요.

🙋‍♀️ 람다: "어? fib(3) 이 두 번이나 나오네요. 같은 걸 또 계산하는 거예요?"

🐬 돌핀쌤: "정확해요! 같은 값을 여러 번 다시 푸는 이걸 중복 계산이라고 해요. n 이 커지면 이 중복이 폭발적으로 늘어나서 재귀가 느려진답니다. 그걸 빠르게 만드는 방법은 아래 '더 해보기'에서 살짝 맛볼게요. 오늘은 우선 기본 재귀부터 손에 익혀요."

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

def fib(n):
    if n <= ___:                      # base case (종료 조건)
        return ___
    return fib(n - ___) + fib(n - ___)   # 앞 두 수를 더함

print(fib(1))   # 1
print(fib(2))   # 1
print(fib(5))   # 5
print(fib(10))  # 55

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
피보나치 수열	앞 두 수를 더해 다음 수를 만듦 `1, 1, 2, 3, 5, 8...`
식	`fib(n) = fib(n-1) + fib(n-2)`
base case	`n <= 2` 일 때 `1` 반환 — 재귀가 멈추는 종료 조건
재귀 호출	자기 자신을 두 번 불러서 결과를 더함
중복 계산	같은 값(`fib(3)` 등)을 여러 번 다시 계산 → 재귀가 느린 원인

🐬 돌핀쌤: "base case로 멈추고, 자기 자신을 두 번 불러 더한다! 이 두 박자면 피보나치 재귀는 끝이에요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요. 전부 오늘 만든 fib 위에 살을 조금 더 붙인 것뿐이에요.

호출 횟수 세어 보기 — 함수 밖에 숫자 변수를 두고 fib 가 불릴 때마다 +1 하면, fib(10) 은 109번, fib(20) 은 13,529번이나 불려요. 중복 계산이 얼마나 심한지 눈으로 보여요. (함수 안에서 바깥 변수를 바꾸려면 global 한 줄이 필요해요.) → 예제로 연습
반복문으로 바꾸기 — a, b = 1, 1 로 시작해 a, b = b, a + b 를 반복하면, 앞 두 값만 기억하며 순식간에 계산해요. 같은 답인데 재귀보다 수만 배 빨라요. → 예제로 연습
메모이제이션 — 한 번 계산한 값을 memo 딕셔너리에 저장해 두고, 같은 값이 또 필요하면 다시 풀지 않고 꺼내 써요. 중복 계산이 사라져서 fib(100) 도 거뜬해요.
@lru_cache 한 줄 — 함수 위에 @lru_cache(maxsize=None) 한 줄만 붙이면 파이썬이 알아서 결과를 기억해 줘요. 메모이제이션을 자동으로 해 주는 셈이에요.

재귀가 너무 깊으면? — RecursionError

함수가 자기 자신을 부를 때마다 컴퓨터는 "나 여기 있어요" 하는 기록을 쌓아요. 파이썬은 기본으로 약 1000번까지만 허용해서, fib(1000) 처럼 너무 깊이 들어가면 RecursionError 가 나요. 깊이를 억지로 늘리기보다는, 위의 반복문으로 바꾸는 게 더 좋은 방법이에요.

자주 하는 실수 두 가지

base case를 빠뜨림 — if n == 1 만 쓰고 fib(2) 처리를 빼면, fib(0), fib(-1)... 로 끝없이 내려가다 멈추지 못해요. n <= 2 처럼 멈출 곳을 넉넉히 잡으세요.
메모를 함수 안에 선언 — 메모이제이션을 쓸 때 memo = {} 를 함수 안에 두면 부를 때마다 새로 비워져서 효과가 없어요. 메모는 함수 밖에 두세요.

11 — 재귀 실습 (피보나치)

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1