한양과학기술고등학교

에듀테크 프로젝트 대시보드

재귀 (Recursion)

재귀 — 자기 자신을 부르는 함수

재귀(recursion)는 함수가 문제를 더 작은 같은 모양의 문제로 쪼개어 자기 자신을 다시 호출하는 방법이다. 핵심은 두 가지 — 더 이상 쪼갤 수 없을 때 멈추는 기저 조건(base case)과, 문제를 한 단계 줄여 자신을 부르는 재귀 호출(recursive case). 아래에서 콜 스택이 어떻게 쌓였다가 풀리는지, 그리고 재귀가 언제 느려지는지 직접 확인해 보자.

1. 콜 스택 — factorial(n) 이 쌓였다 풀린다

4
factorial(4) 호출 준비
↑ 스택 위(마지막 호출)
준비
재귀 호출은 내려갈 때 스택에 프레임을 쌓고, 기저 조건(n ≤ 1)에 닿으면 올라오면서 값을 하나씩 반환하며 프레임을 제거한다.
단계 0 / 0
# 파이썬 def factorial(n): if n <= 1: # 기저 조건: 멈추는 지점 return 1 return n * factorial(n - 1) # 재귀 호출: 문제를 1단계 줄인다

2. 재귀 트리 — fib(n) 은 왜 느릴까

6
—
총 함수 호출 수
—
fib(n) 결과
—
메모로 절약한 호출
같은 색(주황) 노드는 똑같은 부분 문제를 다시 계산하는 중복 호출이다. 메모이제이션을 켜면 한 번 구한 fib(k)를 표에 저장해 두 번째부터는 바로 꺼내 쓴다 — 호출 수가 지수(2ⁿ)에서 선형(n)으로 줄어든다.

3. 재귀를 만들 때 꼭 지킬 것

기저 조건

재귀를 멈추는 가장 작은 경우. 이게 없거나 도달 못 하면 함수가 영원히 자신을 부른다.

수렴

재귀 호출마다 입력이 반드시 기저 조건 쪽으로 작아져야 한다. n-1, 배열 절반 처럼.

믿음의 도약

"더 작은 입력에 대해선 함수가 옳게 동작한다"고 가정하고, 그 결과를 조합해 현재 답을 만든다.

스택 오버플로우 주의 — 호출마다 콜 스택에 프레임이 쌓이므로, 재귀가 너무 깊으면 (파이썬은 기본 약 1000단계) RecursionError가 난다. 깊이가 매우 커질 수 있는 문제는 반복문 + 명시적 스택으로 바꾸거나 꼬리 재귀/메모이제이션을 고려한다.

4. 같은 일을 반복문으로

# 재귀 (읽기 쉬움, 스택 사용) def sum_to(n): if n == 0: return 0 return n + sum_to(n - 1) # 반복 (스택 안 씀, 깊이 제한 없음) def sum_to_loop(n): total = 0 for i in range(1, n + 1): total += i return total

트리·그래프 탐색, 분할 정복(퀵/병합 정렬), 하노이 탑처럼 구조 자체가 재귀적인 문제는 재귀로 짜면 코드가 훨씬 짧고 명확하다. 단순 누적·카운트는 반복문이 보통 더 낫다.

자주 나오는 질문

재귀는 항상 반복문보다 느린가요?

함수 호출 비용(스택 프레임 생성)이 있어 보통 조금 느리고 메모리도 더 씁니다. 하지만 fib처럼 메모이제이션을 곁들이면 알고리즘 자체가 빨라져서, 순진한 반복 구현보다 빠를 수도 있습니다. 중요한 건 언어 문법이 아니라 중복 계산을 하느냐입니다.

기저 조건을 빼먹으면 어떻게 되나요?

함수가 멈추지 않고 자신을 계속 부르다가 콜 스택이 가득 차서 RecursionError(파이썬) / Stack Overflow(대부분 언어)로 프로그램이 죽습니다. 데모 2에서 n을 줄이는 부분을 지웠다고 상상해 보세요.

메모이제이션과 동적 계획법(DP)은 같은 건가요?

둘 다 "부분 문제 답을 저장해 재사용"한다는 아이디어는 같습니다. 메모이제이션은 재귀 + 캐시(위에서 아래로), 전형적인 DP는 작은 문제부터 표를 채우는 반복(아래에서 위로) 방식이라는 차이가 있습니다.

꼬리 재귀(tail recursion)가 뭔가요?

재귀 호출이 함수의 맨 마지막 동작이고 그 결과에 추가 연산을 하지 않는 형태입니다. 일부 언어(스킴, 스칼라 등)는 이를 반복문처럼 최적화해 스택을 안 늘립니다. 다만 파이썬·자바는 이 최적화를 하지 않습니다.