[정글 베이직 5] 재귀 함수 완성

 

 

코드는 바로 맞았다.

힌트에 구조가 다 나와 있었고, 채워 넣었더니 테스트가 통과됐다.
근데 뭔가 찜찜했다. 내가 이해하고 쓴 건지, 그냥 베껴 쓴 건지.

그래서 코드를 닫고 factorial(5)를 손으로 직접 따라가봤다.
함수가 몇 번 불리는지, 어느 시점에 값이 돌아오는지.
그때서야 재귀가 뭔지 실제로 납득됐다.

---

문제 소개

재귀 함수로 팩토리얼과 피보나치 수를 계산한다.
핵심은 코드를 짜는 것보다 재귀의 두 구성요소를 이해하는 것이다.

항목	내용
입력	n: 양의 정수
팩토리얼 출력	n!  →  factorial(5) = 120
피보나치 출력	n번째 피보나치 수  →  fibonacci(5) = 5
핵심 개념	base case, recursive case, 호출 스택

# 팩토리얼
factorial(5)  →  120   # 5×4×3×2×1

# 피보나치  (수열: 0, 1, 1, 2, 3, 5, 8, ...)
fibonacci(5)  →  5     # 인덱스 5번째 값

---

재귀의 두 구성요소

재귀 함수는 반드시 두 가지를 가져야 한다.

구성요소	역할	없으면
base case	더 이상 자기 자신을 부르지 않고 값을 반환	RecursionError — 무한 호출
recursive case	자기 자신을 더 작은 n으로 호출	재귀가 아닌 그냥 일반 함수

핵심 조건 하나: recursive case에서 n이 반드시 작아져야 한다.
작아지지 않으면 base case에 영원히 도달하지 못한다.

---

팩토리얼 — factorial(n)

def factorial(n):
    if n == 0 or n == 1:      # base case
        return 1
    return n * factorial(n-1) # recursive case

factorial(5) 호출 흐름을 직접 따라가면

호출이 쌓이는 구간과, 값이 돌아오는 구간이 분리된다.

# ── 호출이 쌓이는 구간 (위→아래) ──
factorial(5)  →  5 * factorial(4)
factorial(4)  →  4 * factorial(3)
factorial(3)  →  3 * factorial(2)
factorial(2)  →  2 * factorial(1)
factorial(1)  →  1               ← base case, 여기서 멈춤

# ── 값이 돌아오는 구간 (아래→위) ──
factorial(1) = 1
factorial(2) = 2 × 1  =   2
factorial(3) = 3 × 2  =   6
factorial(4) = 4 × 6  =  24
factorial(5) = 5 × 24 = 120

호출이 쌓이고 → base case에서 멈추고 → 반대 방향으로 값이 돌아온다.
이 흐름이 재귀의 전부다.

---

피보나치 — fibonacci(n)

def fibonacci(n):
    if n == 0: return 0        # base case 1
    if n == 1: return 1        # base case 2
    return fibonacci(n-1) + fibonacci(n-2)  # recursive case

팩토리얼과 다른 점이 두 가지 있다.

	팩토리얼	피보나치
base case 수	1개 (n==0 or n==1)	2개 (n==0), (n==1)
recursive case	자기 자신을 1번 호출	자기 자신을 2번 호출
호출 구조	일직선	트리 형태로 가지치기

fibonacci(5) 호출 트리

                      fib(5)
                   /          \
              fib(4)          fib(3)
             /      \         /     \
         fib(3)   fib(2)   fib(2)  fib(1)
         /    \    /   \    /   \
      fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
      /    \
   fib(1) fib(0)

# 모든 잎이 fib(0)=0 또는 fib(1)=1 에서 멈춘다
# 결과: 3 + 2 = 5

트리를 보면 같은 값이 반복해서 계산되는 게 보인다.
fib(3)이 2번, fib(2)이 3번 등장한다.
n이 커질수록 이 중복이 기하급수적으로 늘어난다.

---

전체 테스트 결과

=== 팩토리얼 ===
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

=== 피보나치 수열 ===
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34

=== 추가 테스트 ===
10!     = 3628800
fib(15) = 610

---

시간복잡도

함수	복잡도	이유
factorial(n)	O(n)	n → n-1 → ... → 1, 총 n번 호출
fibonacci(n)	O(2ⁿ)	호출마다 두 갈래로 나뉨, 트리 노드 수 ≈ 2ⁿ

피보나치 O(2ⁿ)는 fib(50)만 돼도 이미 수십억 번 호출이다.
해결책은 메모이제이션 — 한 번 계산한 값을 저장해두고 재사용하면 O(n)으로 줄어든다.

# 메모이제이션 버전 (참고용)
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_fast(n):
    if n == 0: return 0
    if n == 1: return 1
    return fibonacci_fast(n-1) + fibonacci_fast(n-2)

# 지금 단계에서 외울 필요는 없다.
# 재귀 피보나치가 느린 이유와 해결 방향만 알아두면 된다.

---

재귀 짤 때 체크리스트

def my_recursive(n):
    # ✅ 1. base case — 언제 멈출지 먼저 써라
    if n <= 1:
        return 기본값

    # ✅ 2. recursive case — n이 반드시 작아지게
    return my_recursive(n-1)  # n이 줄어드는지 확인

체크	항목
☑	base case가 있는가
☑	recursive case에서 n이 작아지는가
☑	base case에 언젠가 도달하는가

---

마무리

코드는 금방 짰다. 납득하는 데 시간이 더 걸렸다.

재귀가 이해됐다는 건 코드를 쓸 수 있다는 게 아니라,
factorial(5) 가 불렸을 때 내부에서 무슨 일이 일어나는지
머릿속에서 단계별로 따라갈 수 있다는 것인 것 같다.

피보나치 트리에서 같은 값이 반복 계산되는 걸 눈으로 확인하고 나서야,
메모이제이션이 왜 필요한지도 자연스럽게 납득됐다.

다음 문제로 넘어갔다.

🌿