재귀: 자기 자신을 호출해 문제를 작은 단위로 분할하는 제어 흐름
재귀(recursion)는 함수가 자신을 호출하여 큰 문제를 동일한 구조의 작은 문제로 쪼개 해결하는 기법이다. 호출 스택(call stack)에 상태가 쌓이는 방식으로 동작하며, 기저 조건(base case)이 없으면 스택 오버플로우(stack overflow)로 이어진다. 트리, 그래프 순회나 분할 정복(divide and conquer) 알고리즘에서
1. 개념
재귀(recursion)는 함수가 실행 도중 자기 자신을 다시 호출하는 프로그래밍 기법이다. 문제를 자신과 동일한 구조를 가진 더 작은 부분 문제로 나누고, 더 이상 나눌 수 없는 가장 작은 단위에서 직접 답을 구한 뒤 그 결과를 조합해 원래 문제의 답을 만든다.
재귀 함수는 반드시 두 가지 요소를 가진다.
- 기저 조건(base case): 더 이상 재귀 호출을 하지 않고 값을 바로 반환하는 조건. 이게 없으면 무한 재귀에 빠진다.
- 재귀 단계(recursive step): 문제를 더 작은 크기로 줄여 자기 자신을 호출하는 부분.
def factorial(n: int) -> int:
if n <= 1: # 기저 조건
return 1
return n * factorial(n - 1) # 재귀 단계
print(factorial(5)) # 1202. 왜 사용하는가
반복문(iteration)으로도 대부분의 문제를 풀 수 있지만, 문제 자체가 재귀적 구조를 가질 때는 재귀가 코드의 가독성과 문제 정의를 훨씬 명확하게 만든다.
- 트리(tree), 그래프(graph) 같은 재귀적 자료구조는 순회 로직이 자연스럽게 재귀 형태로 표현된다.
- 분할 정복(divide and conquer) 알고리즘(퀵정렬, 병합정렬, 이진 탐색)은 "문제를 절반으로 나누고 각각 해결 후 합친다"는 정의 자체가 재귀와 일치한다.
- 백트래킹(backtracking), 완전 탐색처럼 상태 공간을 탐색하는 문제에서 스택 관리를 언어 런타임에 위임할 수 있다.
반대로 단순 반복 계산이라면 재귀는 함수 호출 오버헤드와 스택 사용량 때문에 반복문보다 불리하다.
3. 동작 원리
함수가 호출될 때마다 런타임은 호출 스택(call stack)에 스택 프레임(stack frame)을 쌓는다. 스택 프레임에는 매개변수, 지역 변수, 반환 주소가 저장된다. 재귀 호출은 기저 조건에 도달할 때까지 계속 프레임을 쌓다가(전개 단계), 기저 조건에서 값이 반환되면 스택을 역순으로 정리하며 값을 조합한다(수렴 단계).
factorial(3)
├─ 3 * factorial(2)
│ ├─ 2 * factorial(1)
│ │ └─ return 1 (기저 조건 도달, 스택 최상단)
│ └─ return 2 * 1 = 2
└─ return 3 * 2 = 6호출 스택은 유한한 메모리 공간(보통 스레드당 수 MB)을 사용하므로, 재귀 깊이가 너무 깊어지면 스택 오버플로우(stack overflow)가 발생한다. Python은 기본 재귀 한도가 1000 정도(sys.getrecursionlimit())로 설정되어 있어 이를 넘으면 RecursionError가 발생한다.
일부 언어(Scheme, Scala 일부 함수)는 꼬리 호출 최적화(tail call optimization)를 지원해 재귀 호출이 마지막 연산일 경우 스택 프레임을 재사용한다. Python과 JavaScript(V8)는 표준적으로 이 최적화를 지원하지 않으므로, 깊은 재귀는 반복문으로 바꾸거나 명시적 스택을 사용해야 한다.
4. 코드 예제
피보나치 수열 – 순수 재귀 vs 메모이제이션(memoization)
import sys
from functools import lru_cache
# 순수 재귀: 중복 계산이 지수적으로 증가한다
def fib_naive(n: int) -> int:
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# 메모이제이션 적용: 이미 계산한 값을 캐시에 저장해 재사용
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
print(fib_naive(20)) # 6765
print(fib_memo(60)) # 1548008755920, 순수 재귀로는 사실상 계산 불가능이진 탐색 – 분할 정복 재귀
def binary_search(arr: list[int], target: int, lo: int = 0, hi: int | None = None) -> int:
if hi is None:
hi = len(arr) - 1
if lo > hi: # 기저 조건: 탐색 실패
return -1
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
data = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(data, 7)) # 3
print(binary_search(data, 4)) # -1재귀 깊이 한계와 반복문 전환
def sum_recursive(n: int) -> int:
if n == 0:
return 0
return n + sum_recursive(n - 1)
# sum_recursive(5000) 은 sys.setrecursionlimit()을 늘리지 않으면 RecursionError 발생
sys.setrecursionlimit(10000)
print(sum_recursive(5000)) # 실행되지만 스택 메모리를 많이 소비한다
# 반복문으로 전환하면 스택 깊이 제약 없이 O(1) 메모리로 동작
def sum_iterative(n: int) -> int:
total = 0
for i in range(n + 1):
total += i
return total
print(sum_iterative(1_000_000)) # 문제 없이 동작5. 시간 복잡도 또는 성능 특성
| 알고리즘 | 시간 복잡도 | 공간 복잡도(호출 스택) | |---|---|---| | factorial(n) | O(n) | O(n) | | 피보나치 순수 재귀 | O(2^n) | O(n) | | 피보나치 메모이제이션 | O(n) | O(n) | | 이진 탐색(재귀) | O(log n) | O(log n) | | 병합 정렬 | O(n log n) | O(n) (병합 버퍼) + O(log n) (호출 스택) |
재귀의 시간 복잡도는 점화식(recurrence relation)으로 분석한다. 예를 들어 병합 정렬은 T(n) = 2T(n/2) + O(n)이며 마스터 정리(master theorem)에 따라 O(n log n)이 도출된다. 순수 재귀 피보나치처럼 하나의 문제가 여러 개의 동일한 부분 문제로 중복 분기되면 지수적으로 시간이 증가하므로, 이런 경우 메모이제이션이나 동적 계획법(dynamic programming)으로 전환해야 한다.
공간 복잡도 측면에서 재귀는 반복문에는 없는 호출 스택 비용이 추가로 발생한다는 점이 핵심 차이다. 반복문은 대부분 O(1) 추가 공간으로 처리 가능한 문제도, 재귀로 구현하면 재귀 깊이만큼 O(n) 스택 공간이 필요하다.
6. 실무 사용 사례
- 파일 시스템 탐색: 디렉터리 트리를 순회하며 하위 폴더를 재귀적으로 탐색하는 로직(
os.walk내부 구현이나 직접 구현하는 재귀적 디렉터리 스캐너). - JSON/트리 구조 직렬화: 중첩된 객체나 배열을 재귀적으로 순회하며 평탄화(flatten)하거나 깊은 복사(deep copy)를 수행.
- 파서(parser)와 컴파일러: 재귀 하향 파서(recursive descent parser)는 문법 규칙 자체가 재귀적이므로 재귀 호출로 자연스럽게 구현된다.
- UI 컴포넌트 트리: React 등에서 중첩된 컴포넌트나 댓글 트리(대댓글 구조)를 렌더링할 때 재귀적으로 자식 노드를 그린다.
- DB 계층형 데이터 조회: PostgreSQL의
WITH RECURSIVE구문으로 조직도, 카테고리 트리 같은 계층 구조를 SQL 레벨에서 재귀적으로 조회한다.
-- 재귀 CTE로 조직도 전체 하위 직원 조회
WITH RECURSIVE subordinates AS (
SELECT id, name, manager_id
FROM employees
WHERE id = 1 -- 시작 지점(기저 조건에 해당)
UNION ALL
SELECT e.id, e.name, e.manager_id
FROM employees e
INNER JOIN subordinates s ON e.manager_id = s.id -- 재귀 단계
)
SELECT * FROM subordinates;7. 주의할 점
- 기저 조건 누락: 기저 조건이 없거나 잘못 설정되면 무한 재귀로 이어져 스택 오버플로우가 발생한다. 재귀 함수를 작성할 때는 기저 조건을 가장 먼저 확정해야 한다.
- 중복 계산: 피보나치처럼 동일한 부분 문제를 여러 번 재계산하는 구조는 메모이제이션이나 동적 계획법으로 반드시 최적화해야 한다.
- 깊은 재귀와 스택 한계: Python은 기본 재귀 한도가 1000이며,
sys.setrecursionlimit()으로 늘릴 수는 있지만 근본적으로 OS 스레드 스택 크기 한계는 그대로 남는다. 데이터 크기가 예측 불가능한 경우(예: 사용자 업로드 트리 데이터) 재귀 대신 반복문 기반 명시적 스택으로 구현하는 편이 안전하다. - 꼬리 호출 최적화 부재: Python, JavaScript는 꼬리 재귀(tail recursion)를 작성해도 최적화되지 않는다. "꼬리 재귀니까 안전하다"는 다른 언어의 가정을 그대로 적용하면 안 된다.
- 디버깅 난이도: 스택 트레이스가 깊어지면 에러 추적이 어려워진다. 재귀 함수에는 로깅이나 깊이 파라미터를 넣어 디버깅을 대비하는 경우가 많다.
8. 핵심 정리
재귀는 문제를 자기 자신과 동일한 구조의 작은 부분 문제로 나누고, 기저 조건에서 값을 반환한 뒤 호출 스택을 따라 결과를 조합하는 기법이다. 트리·그래프 순회, 분할 정복, 백트래킹처럼 문제 자체가 재귀적 구조를 가질 때 코드가 가장 명확해진다. 다만 호출 스택 메모리 비용과 중복 계산 가능성을 항상 고려해야 하며, 필요하다면 메모이제이션이나 반복문 기반 구현으로 전환하는 판단이 실무에서 중요하다.