Ch.9 재귀와 백트래킹
재귀의 본질 — base case, recursive case, factorial
함수가 자기 자신을 다시 호출한다?
거울 앞에 거울을 놓으면 무한히 반사됩니다. 재귀도 마찬가지입니다 — 자기 자신을 호출하지만, 멈추는 조건이 없으면 무한루프에 빠집니다.
어디서 멈춰야 하는지, 어떻게 결과가 합쳐지는지 처음엔 혼란스럽습니다.
base case로 멈추고, recursive case로 쪼개는 두 가지 원칙만 잡으면 재귀는 강력한 도구가 됩니다.
핵심 개념
재귀 (Recursion)
함수가 자기 자신을 호출하여 문제를 해결하는 기법
Base Case
재귀를 멈추는 종료 조건
Recursive Case
문제를 더 작은 부분으로 쪼개어 자기 자신을 호출하는 부분
핵심 내용
러시아 인형 마트료시카를 아시나요?
큰 인형을 열면 작은 인형이 나오고, 그 안에 또 작은 인형이 있습니다
가장 작은 인형에 도달하면 더 이상 열 수 없습니다. 이것이 바로 Base Case입니다
재귀 = 자기 자신을 호출하되, 반드시 멈추는 조건(Base Case)이 있어야 한다
5! = 5 × 4 × 3 × 2 × 1 = 120 이것을 재귀로 표현해봅시다
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!
def factorial(n):
# Base Case: 멈추는 조건
if n <= 1:
return 1
# Recursive Case: 자기 자신 호출
return n * factorial(n - 1)
print(factorial(5)) # 120n=5일 때 함수가 5번 호출되고, base case에 도달하면 역순으로 값을 곱해 올라갑니다
피보나치 수열도 재귀의 대표 예시입니다
def fib(n):
if n <= 1: # Base Case
return n
return fib(n-1) + fib(n-2) # Recursive Case
# fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5fib(5)를 구하면 fib(2)가 3번 중복 호출됩니다. 시간 복잡도가 O(2ⁿ)으로 폭발합니다
이 중복 문제는 나중에 메모이제이션(DP)으로 해결합니다. 지금은 재귀 구조 자체에 집중합시다
모든 재귀 함수는 3단계로 설계할 수 있습니다
1단계: Base Case 정의 — 가장 작은 입력에서 바로 답을 반환 2단계: Recursive Case — 현재 문제를 더 작은 문제로 쪼개기 3단계: 결과 합치기 — 재귀 호출 결과를 현재 답에 결합
# 예: 배열의 합을 재귀로 구하기
def array_sum(arr):
if len(arr) == 0: # 1. Base Case
return 0
return arr[0] + array_sum(arr[1:]) # 2+3. 쪼개고 합치기
print(array_sum([1, 2, 3, 4])) # 10arr[0]을 꺼내고 나머지 arr[1:]을 재귀 호출. base case(빈 배열)에서 0을 반환하면 역순으로 합산됩니다
재귀가 특히 강력한 문제 유형이 있습니다
트리 탐색 — 자식 노드를 재귀적으로 방문 분할 정복 — 문제를 반으로 나누어 풀기 백트래킹 — 경우의 수를 탐색하고 되돌아오기 수학적 정의 — 팩토리얼, 피보나치 등
문제가 자기 자신의 작은 버전으로 정의될 때 재귀를 쓴다. 그렇지 않으면 반복문이 더 효율적입니다
다음 재귀 함수에서 Base Case는 어느 부분인가?
def count(n):
if n == 0:
return 0
return 1 + count(n - 1)factorial(4)를 호출하면 함수가 총 몇 번 호출되는가?
핵심 용어
재귀 (Recursion)
함수가 자기 자신을 호출하여 문제를 해결하는 기법
Base Case
재귀를 멈추는 종료 조건
Recursive Case
문제를 더 작은 부분으로 쪼개어 자기 자신을 호출
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작