1. 재귀(Recursion)란?
재귀는 함수가 자기 자신을 호출하는 기법
하지만 이 한 줄로는 이해가 어려움!
중요한 건 재귀 호출이 “트리”처럼 확장되며 진행
- Level (깊이): 현재 함수가 몇 번째 단계에서 실행되고 있는지. 호출 스택의 깊이
- Branch (가지): 한 호출이 여러 재귀 호출로 갈라져 나가는 경로
따라서 재귀는 “Level이 깊어지면서 Branch가 나뉘고, 다시 Base Case에서 위로 합쳐지며 값이 반환되는 과정”
2. 기본 구조
function recursive(parameter):
if (종료 조건): // Base Case
return 결과
else: // Recursive Case
recursive(더 작은 문제)
return 결과Base Case: 더 이상 호출하지 않고 종료하는 조건. 없으면 무한루프 발생
Recursive Case: 문제를 더 작은 단위로 쪼개어 자기 자신을 호출
3-1. 예시 1 팩토리얼
수학적 정의
n! = n × (n-1)!
0! = 1파이썬 코드 (주석 포함)
def factorial(n, level=0):
# level은 현재 함수 호출 깊이를 나타냄
indent = " " * level
print(f"{indent}▶ factorial({n}) 호출 (level={level})")
if n == 0: # Base Case
print(f"{indent}◀ Base Case 도달: factorial(0)=1 반환")
return 1
# Recursive Case
# 현재 n을 다음 호출(factorial(n-1)) 결과와 곱함
result = n * factorial(n-1, level+1)
print(f"{indent}◀ factorial({n}) = {n} * factorial({n-1}) = {result} (level={level})")
return result
print("최종 결과:", factorial(3))실행 흐름
▶ factorial(3) 호출 (level=0)
▶ factorial(2) 호출 (level=1)
▶ factorial(1) 호출 (level=2)
▶ factorial(0) 호출 (level=3)
◀ Base Case 도달: factorial(0)=1 반환
◀ factorial(1) = 1 * factorial(0) = 1 (level=2)
◀ factorial(2) = 2 * factorial(1) = 2 (level=1)
◀ factorial(3) = 3 * factorial(2) = 6 (level=0)
최종 결과: 6여기서 인자 변화를 보면:
- 첫 호출:
n=3 - 다음 호출:
n=2 - 그 다음:
n=1 - 마지막:
n=0(Base Case)
이전 호출의 인자(
n)가 한 단계 줄어든 값으로 다음 호출에 전달되고,
반환값이 거꾸로 올라오면서 곱해짐
3-2. 예시 2 피보나치
정의
F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2)코드
def fib(n, level=0):
indent = " " * level
print(f"{indent}▶ fib({n}) 호출 (level={level})")
if n == 0:
print(f"{indent}◀ Base Case: fib(0)=0 반환")
return 0
if n == 1:
print(f"{indent}◀ Base Case: fib(1)=1 반환")
return 1
# Branch: 두 방향으로 갈라짐
left = fib(n-1, level+1) # fib(n-1)
right = fib(n-2, level+1) # fib(n-2)
result = left + right
print(f"{indent}◀ fib({n}) = {left}+{right}={result} (level={level})")
return result
print("최종 결과:", fib(4))실행 흐름 (fib(4))
▶ fib(4) 호출 (level=0)
▶ fib(3) 호출 (level=1)
▶ fib(2) 호출 (level=2)
▶ fib(1) 호출 (level=3)
◀ Base Case: fib(1)=1 반환
▶ fib(0) 호출 (level=3)
◀ Base Case: fib(0)=0 반환
◀ fib(2) = 1+0=1 (level=2)
▶ fib(1) 호출 (level=2)
◀ Base Case: fib(1)=1 반환
◀ fib(3) = 1+1=2 (level=1)
▶ fib(2) 호출 (level=1)
...
◀ fib(4) = 2+1=3 (level=0)Branch 강조:
fib(n)은 항상fib(n-1)과fib(n-2)두 갈래(branch)로 분기
인자 연관성: 현재n값에서 두 개의 작은 문제(n-1,n-2)로 쪼깸
3-3. 예시 3 하노이탑
규칙
- N-1개를 보조 기둥으로 옮김 (branch 1)
- 가장 큰 원판을 목표 기둥으로 옮김 (base 작업)
- N-1개를 목표 기둥으로 옮김 (branch 2)
코드
def hanoi(n, start, target, auxiliary, level=0):
indent = " " * level
if n == 1:
print(f"{indent}Move disk 1 from {start} → {target}")
return
# Branch 1: N-1개를 start→auxiliary
hanoi(n-1, start, auxiliary, target, level+1)
print(f"{indent}Move disk {n} from {start} → {target}")
# Branch 2: N-1개를 auxiliary→target
hanoi(n-1, auxiliary, target, start, level+1)
hanoi(3, 'A', 'C', 'B')실행 결과
Move disk 1 from A → C
Move disk 2 from A → B
Move disk 1 from C → B
Move disk 3 from A → C
Move disk 1 from B → A
Move disk 2 from B → C
Move disk 1 from A → CLevel: 원판 개수(n)가 줄어들며 재귀 깊이가 깊어짐
Branch: "왼쪽 branch → 중앙 작업 → 오른쪽 branch"
4. 흔히 헷갈리는 지점
❌ 오개념 1: “재귀가 무한히 돌 것 같다”
- 종료 조건(Base Case)이 반드시 있어야 함
- 종료 조건이 없으면 스택이 무한히 쌓여
RecursionError발생
❌ 오개념 2: “return 값이 어디로 가는지 모르겠다”
- return 값은 호출한 함수로 되돌아간다.
- 즉,
factorial(0)이 1을 반환하면 →factorial(1)에서1*1=1계산 → 다시 반환 →factorial(2)로 전달 → 이런 식으로 거슬러 올라감
❌ 오개념 3: “모든 호출이 동시에 실행된다”
- 사실은 스택 구조로 순서대로 실행
- 먼저 깊이 들어가고(Base Case까지), 그 다음에 하나씩 반환하며 위로 올라옴
5. 재귀의 의미와 활용
- Level: 호출 스택의 깊이 → 트리 탐색, DFS에서 “현재 깊이” 표현 가능
- Branch: 문제를 나누는 방식 → 분할 정복(merge sort, quick sort)이나 그래프 탐색에서 확장되는 경로
즉, 재귀의 핵심은 “함수 호출 스택이 트리처럼 확장되며, 인자(parameter)가 작아지거나 바뀌면서 Base Case까지 진행한 후 다시 위로 합쳐지는 과정”을 이해하는 것
6. 추천 백준 문제 (재귀 연습)
-
백준 10870번 피보나치 수 5
→ 기본 재귀 호출과 Base Case/Recursive Case 감 잡기 -
백준 17478번 재귀함수가 뭔가요?
→ level(깊이)에 따라 다른 출력이 필요한 문제. 재귀 구조 이해하기에 최적 -
백준 11729번 하노이 탑 이동 순서
→ 재귀적 사고를 트리 구조로 확장해보는 문제
