Ch.9 재귀와 백트래킹
재귀→반복 변환 — 콜스택 시각화, Explicit Stack
재귀는 편하지만 스택이 넘친다?
재귀 함수를 호출하면 내부적으로 콜스택(Call Stack)에 프레임이 쌓입니다. 입력이 크면 RecursionError: maximum recursion depth exceeded를 만나게 됩니다.
편리한 재귀를 포기해야 할까? 반복문으로 바꿀 수 있을까?
명시적 스택을 사용하면 재귀의 논리를 그대로 유지하면서 스택 오버플로우를 피할 수 있습니다.
핵심 개념
콜스택 (Call Stack)
함수 호출 시마다 쌓이는 실행 컨텍스트의 스택
스택 프레임
각 함수 호출의 지역 변수, 매개변수, 복귀 주소를 저장하는 메모리 블록
핵심 내용
함수를 호출하면 컴퓨터 내부에서 프레임이 스택처럼 쌓입니다
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
factorial(4)
# 콜스택: factorial(4) → factorial(3) → factorial(2) → factorial(1)
# 반환: 1 → 2 → 6 → 24factorial(4) 호출 시 4개의 프레임이 쌓입니다. n=1에서 반환이 시작되면 아래서부터 하나씩 pop됩니다
Python의 기본 재귀 깊이 제한은 1,000입니다
import sys
print(sys.getrecursionlimit()) # 1000
# 큰 입력 → 스택 오버플로우
factorial(10000)
# RecursionError: maximum recursion depth exceeded면접에서 재귀 풀이를 제시한 뒤 "입력이 크면 반복으로 변환 가능합니다"라고 말하면 가산점!
가장 간단한 재귀→반복 변환: 꼬리 재귀는 루프로 바로 치환됩니다
# 재귀 버전
def factorial_rec(n):
if n <= 1:
return 1
return n * factorial_rec(n - 1)# 반복 버전 — O(n) 시간, O(1) 공간!
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result재귀: O(n) 공간 (콜스택) 반복: O(1) 공간 (변수 하나)
트리/그래프 DFS는 명시적 스택으로 변환합니다
# 재귀 DFS (이진 트리)
def dfs_recursive(node):
if not node:
return
print(node.val)
dfs_recursive(node.left)
dfs_recursive(node.right)# 반복 DFS — Explicit Stack
def dfs_iterative(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val)
# 오른쪽 먼저 push → 왼쪽이 먼저 pop
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)핵심: 콜스택 대신 리스트를 스택으로 사용한다. 재귀의 논리가 그대로 유지됩니다
꼬리 재귀(Tail Recursion)란 재귀 호출이 함수의 마지막 연산인 경우입니다
# 꼬리 재귀 Factorial
def factorial_tail(n, acc=1):
if n <= 1:
return acc
return factorial_tail(n - 1, n * acc) # 마지막 연산 = 재귀 호출
# 일반 재귀는 'n * factorial(n-1)' → 곱셈이 마지막 연산
# 꼬리 재귀는 결과를 acc에 누적 → 추가 연산 없음주의: Python은 TCO를 지원하지 않습니다! Java, JavaScript도 마찬가지. Scala, Kotlin, Scheme 등은 TCO 지원. 면접에서 TCO 개념을 알고 있다고 말하면 좋은 인상을 줍니다.
재귀 함수 호출 시 콜스택에 쌓이는 정보가 아닌 것은?
재귀를 반복으로 변환할 때 콜스택을 대체하는 자료구조는?
재귀 factorial의 공간 복잡도는? (입력 n)
핵심 용어
콜스택
함수 호출 시마다 쌓이는 실행 컨텍스트의 스택
스택 프레임
지역 변수, 매개변수, 복귀 주소를 저장하는 블록
Explicit Stack
리스트/배열로 직접 구현한 스택 자료구조
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작