19. 재귀 함수 - 자기 자신을 호출하는 함수

재귀 함수

19. 재귀 함수 - 자기 자신을 호출하는 함수

거울 앞에 거울을 놓으면 무한히 반사되는 것처럼, 함수가 자기 자신을 호출하는 것을 재귀라고 한다. 처음엔 머리가 아프지만, 익숙해지면 복잡한 문제를 놀랍도록 간결하게 풀 수 있다.

---

재귀 함수란?

재귀 함수(Recursive Function)는 함수 내부에서 자기 자신을 다시 호출하는 함수다.

def countdown(n):
    if n <= 0:
        print("발사!")
        return          # 종료 조건 (base case)
    print(n)
    countdown(n - 1)    # 자기 자신 호출

countdown(5)
# 5
# 4
# 3
# 2
# 1
# 발사!

재귀의 두 가지 필수 요소

1. 종료 조건 (Base Case) — 재귀를 멈추는 조건. 없으면 무한 루프!
2. 재귀 호출 (Recursive Case) — 문제를 더 작은 문제로 쪼개서 자기 자신 호출

def func(n):
    if n == 0:          # 1. 종료 조건
        return
    # ...
    func(n - 1)         # 2. 재귀 호출 (더 작은 문제)

---

팩토리얼 (Factorial)

n! = n × (n-1) × (n-2) × ... × 1

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 0! = 1 (수학적 정의)

반복문 방식

def factorial_loop(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_loop(5))    # 120

재귀 방식

def factorial(n):
    if n <= 1:          # 종료 조건
        return 1
    return n * factorial(n - 1)    # n! = n × (n-1)!

print(factorial(5))    # 120

 

재귀 호출 스택

호출 과정 추적

def factorial(n):
    print(f"factorial({n}) 호출")
    if n <= 1:
        print(f"factorial({n}) = 1 반환 (종료 조건)")
        return 1
    result = n * factorial(n - 1)
    print(f"factorial({n}) = {n} × factorial({n-1}) = {result} 반환")
    return result

factorial(4)
# factorial(4) 호출
# factorial(3) 호출
# factorial(2) 호출
# factorial(1) 호출
# factorial(1) = 1 반환 (종료 조건)
# factorial(2) = 2 × factorial(1) = 2 반환
# factorial(3) = 3 × factorial(2) = 6 반환
# factorial(4) = 4 × factorial(3) = 24 반환

---

피보나치 수열 (Fibonacci)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

규칙: F(n) = F(n-1) + F(n-2) (앞의 두 수를 더한 것)

재귀 방식

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

for i in range(10):
    print(fib(i), end=" ")
# 0 1 1 2 3 5 8 13 21 34

문제: 중복 계산

fib(5)를 구하면 fib(3)이 2번, fib(2)가 3번 호출된다. n이 커지면 기하급수적으로 느려진다.

import time

start = time.time()
print(fib(35))    # 9227465
print(f"소요 시간: {time.time() - start:.2f}초")
# 소요 시간: 약 3~5초 (매우 느림!)

해결: 메모이제이션 (Memoization)

이미 계산한 결과를 저장해두고 재활용한다.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

start = time.time()
print(fib_memo(35))    # 9227465
print(f"소요 시간: {time.time() - start:.6f}초")
# 소요 시간: 0.000xxx초 (거의 즉시!)

반복문 방식 (가장 효율적)

def fib_loop(n):
    if n <= 0:
        return 0
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print(fib_loop(35))    # 9227465

---

하노이 탑 (Tower of Hanoi)

재귀의 대표적인 고전 문제. 3개의 기둥과 n개의 원판이 있다.

규칙:

1. 한 번에 하나의 원판만 옮길 수 있다
2. 큰 원판 위에 작은 원판만 올릴 수 있다
3. 모든 원판을 A에서 C로 옮기면 된다

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"원판 1: {source} → {target}")
        return
    # 1. n-1개를 보조 기둥으로 이동
    hanoi(n - 1, source, auxiliary, target)
    # 2. 가장 큰 원판을 목표 기둥으로 이동
    print(f"원판 {n}: {source} → {target}")
    # 3. n-1개를 보조 기둥에서 목표 기둥으로 이동
    hanoi(n - 1, auxiliary, target, source)

print("=== 원판 3개 ===")
hanoi(3, "A", "C", "B")
# 원판 1: A → C
# 원판 2: A → B
# 원판 1: C → B
# 원판 3: A → C
# 원판 1: B → A
# 원판 2: B → C
# 원판 1: A → C

💡 원판 n개의 최소 이동 횟수는 2^n - 1이다. 3개면 7번, 10개면 1023번!

---

재귀 vs 반복 비교

재귀 vs 반복 비교

# 1부터 n까지의 합

# 재귀 방식
def sum_recursive(n):
    if n <= 0:
        return 0
    return n + sum_recursive(n - 1)

# 반복 방식
def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

print(sum_recursive(100))    # 5050
print(sum_loop(100))         # 5050

언제 재귀를 쓸까?

• 트리 구조 탐색 (폴더/파일 구조)
• 분할 정복 알고리즘 (퀵정렬, 병합정렬)
• 수학적 점화식 (팩토리얼, 피보나치)
• 문제가 작은 동일 문제로 분해되는 경우

---

재귀 한계와 주의사항

최대 재귀 깊이

파이썬은 기본적으로 1000번까지만 재귀 호출을 허용한다.

def infinite_recursion(n):
    print(n)
    infinite_recursion(n + 1)

infinite_recursion(1)
# RecursionError: maximum recursion depth exceeded

재귀 깊이 확인 및 변경

import sys

print(sys.getrecursionlimit())    # 1000 (기본값)

sys.setrecursionlimit(2000)       # 변경 가능 (권장하지 않음)

⚠️ 재귀 깊이를 무작정 늘리면 스택 오버플로가 발생할 수 있다. 깊은 재귀가 필요하면 반복문으로 변환하는 것이 안전하다.

재귀를 반복으로 변환

# 재귀 버전
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

# 반복 버전 (스택 안전)
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# 둘 다 같은 결과
print(factorial_rec(10))     # 3628800
print(factorial_iter(10))    # 3628800

---

실전 예시: 중첩 리스트 평탄화

재귀가 빛을 발하는 실전 예시: 중첩된 리스트를 1차원으로 펴기

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))    # 재귀 호출
        else:
            result.append(item)
    return result

nested = [1, [2, 3], [4, [5, 6]], [[7, 8], 9]]
print(flatten(nested))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

디렉토리 구조 출력 (개념)

def print_tree(data, indent=0):
    for key, value in data.items():
        print("  " * indent + str(key))
        if isinstance(value, dict):
            print_tree(value, indent + 1)    # 재귀
        else:
            print("  " * (indent + 1) + str(value))

folder = {
    "프로젝트": {
        "src": {
            "main.py": "메인 파일",
            "utils.py": "유틸리티",
        },
        "docs": {
            "readme.md": "설명서",
        },
        "setup.py": "설정 파일",
    }
}
print_tree(folder)
# 프로젝트
#   src
#     main.py
#       메인 파일
#     utils.py
#       유틸리티
#   docs
#     readme.md
#       설명서
#   setup.py
#     설정 파일

---

직접 해보기

문제 1. 재귀 함수로 1부터 n까지의 곱을 구하는 product(n) 함수를 만들어보자. (팩토리얼과 동일)

문제 2. 재귀 함수로 문자열을 뒤집는 reverse_str(s) 함수를 만들어보자.

문제 3. 재귀 함수로 리스트의 합을 구하는 list_sum(lst) 함수를 만들어보자. (내장 sum 사용 금지)

문제 4. 재귀 함수로 거듭제곱을 계산하는 power(base, exp) 함수를 만들어보자. (2^10 = 1024)

문제 5. 하노이 탑에서 원판 4개일 때의 이동 과정을 출력해보자. 총 몇 번 이동하는지 세어보자.

정답 보기

# 문제 1
def product(n):
    if n <= 1:
        return 1
    return n * product(n - 1)
‍
print(product(5))    # 120
print(product(10))   # 3628800
‍
# 문제 2
def reverse_str(s):
    if len(s) <= 1:
        return s
    return reverse_str(s[1:]) + s[0]
‍
print(reverse_str("hello"))     # olleh
print(reverse_str("파이썬"))    # 썬이파
‍
# 문제 3
def list_sum(lst):
    if not lst:
        return 0
    return lst[0] + list_sum(lst[1:])
‍
print(list_sum([1, 2, 3, 4, 5]))    # 15
print(list_sum([10, 20, 30]))        # 60
‍
# 문제 4
def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)
‍
print(power(2, 10))    # 1024
print(power(3, 4))     # 81
‍
# 문제 5
count = 0
def hanoi(n, source, target, auxiliary):
    global count
    if n == 1:
        print(f"원판 1: {source} → {target}")
        count += 1
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"원판 {n}: {source} → {target}")
    count += 1
    hanoi(n - 1, auxiliary, target, source)
‍
hanoi(4, "A", "C", "B")
print(f"\n총 이동 횟수: {count}")    # 15

---

오늘의 정리

항목	내용
재귀 함수	자기 자신을 호출하는 함수
종료 조건	재귀를 멈추는 조건 (base case). 반드시 필요!
팩토리얼	n! = n × (n-1)!, 종료: 1! = 1
피보나치	F(n) = F(n-1) + F(n-2), 메모이제이션으로 최적화
하노이 탑	분할 정복의 대표 문제. 이동 횟수: 2^n - 1
재귀 한계	기본 1000회. sys.getrecursionlimit()으로 확인
재귀 vs 반복	재귀는 간결하지만 느릴 수 있음. 상황에 맞게 선택

---

다음 편 예고: 데코레이터와 제너레이터 - 중급으로 가는 관문

함수를 감싸는 함수? yield로 값을 하나씩 내보내기? 파이썬 중급의 핵심 문법인 데코레이터와 제너레이터를 배워보자.

---

태그: 파이썬 Python 파이썬독학 재귀함수 recursion 팩토리얼 피보나치 알고리즘 파이썬기초 IT교육