재귀 함수 (Recursion)
도입
어떤 문제를 더 작은 하위 문제로 쪼개고, 그 하위 문제를 같은 방식으로 반복해서 해결하는 함수 작성 기법입니다. 반복문과 달리, 재귀는 “문제를 구조적으로 표현하는 방식”에 가깝기 때문에 트리, 그래프, 분할 정복, 백트래킹, DFS 같은 알고리즘에서 매우 자주 등장합니다.
처음에는 재귀가 낯설고 무한 호출처럼 보일 수 있지만, 실제로는 종료 조건(base case)과 자기 자신을 더 작은 입력으로 호출하는 규칙(recursive case)만 정확히 설계하면 매우 강력한 풀이 방식이 됩니다. 즉, 재귀의 핵심은 문법이 아니라 문제를 자기 닮은 꼴 구조로 보는 사고입니다.
필요성
배열 순회처럼 단순한 문제는 반복문이 더 직관적일 수 있습니다. 하지만 폴더 구조 순회, 트리 탐색, 부분집합 생성, 순열 생성, 미로 탐색, 분할 정복처럼 “현재 문제를 같은 형태의 더 작은 문제로 나눌 수 있는 경우”에는 재귀가 오히려 훨씬 자연스럽습니다.
- 트리 순회
- DFS 탐색
- 백트래킹
- 분할 정복
- 하노이 탑 같은 자기 닮은 꼴 문제
- 팩토리얼, 피보나치 같은 점화식 기반 문제
- 폴더 / 조직도 / DOM 같은 계층 구조 탐색
정의
재귀 함수는 이름 그대로 함수 내부에서 자기 자신을 다시 호출합니다. 하지만 단순히 자기 자신을 부르는 것만으로는 재귀가 아닙니다. 올바른 재귀가 되려면 반드시 두 가지가 필요합니다.
| 구성 요소 | 의미 | 없으면 생기는 문제 |
|---|---|---|
| 종료 조건(Base Case) | 더 이상 재귀 호출을 하지 않고 바로 답을 반환하는 조건 | 무한 호출 |
| 재귀 단계(Recursive Case) | 문제를 더 작은 입력으로 바꾸어 자기 자신을 호출하는 부분 | 문제 축소 실패, 종료 불가 |
작동 원리
재귀 함수가 호출될 때마다 현재 지역 변수, 매개변수, 돌아갈 위치 같은 정보가 호출 스택(call stack)에 쌓입니다. 그리고 가장 안쪽 호출이 종료되면, 쌓였던 스택이 하나씩 빠지면서 이전 호출로 돌아갑니다.
f(3)
→ f(2)
→ f(1)
→ f(0) // 종료 조건
← 돌아옴
← 돌아옴
← 돌아옴이 구조 때문에 재귀는 “내려가는 단계”와 “돌아오는 단계”를 나누어 생각하는 것이 중요합니다. 어떤 문제는 호출 전에 작업하고, 어떤 문제는 돌아오면서 작업합니다.
가장 기본 예시
팩토리얼은 n! = n * (n-1)! 형태이므로 재귀로 표현하기 좋습니다. 종료 조건도 0! = 1처럼 명확합니다.
static int factorial(int n) {
if (n == 0) return 1; // 종료 조건
return n * factorial(n - 1); // 재귀 단계
}이 예시에서 중요한 것은 팩토리얼 공식을 외우는 것이 아니라, 큰 문제를 같은 구조의 더 작은 문제 하나로 줄였다는 점입니다.
재귀를 떠올리는 신호
- 문제가 자기보다 작은 같은 문제로 나뉜다.
- 트리나 계층 구조처럼 자식 문제를 다시 같은 방식으로 처리해야 한다.
- 모든 경우를 생성해야 한다.
- 현재 선택 후 나머지 경우를 다시 탐색해야 한다.
- 점화식 형태가 보인다.
- 반복문으로 짜려면 스택을 직접 구현해야 할 것 같다.
패턴 1. 분할 정복
병합 정렬, 퀵 정렬, 이진 탐색 트리 처리처럼 큰 문제를 더 작은 부분 문제로 나누고, 그 결과를 다시 합치는 문제는 재귀와 잘 맞습니다.
static void divide(int left, int right) {
if (left == right) return;
int mid = (left + right) / 2;
divide(left, mid);
divide(mid + 1, right);
// 여기서 두 결과를 합치는 작업
}이 패턴은 “작게 나누고, 각각 해결하고, 다시 합친다”는 구조만 잡히면 이해가 쉬워집니다.
패턴 2. 트리 순회
트리의 각 노드는 왼쪽 서브트리와 오른쪽 서브트리를 가질 수 있습니다. 이 서브트리도 결국 트리이므로, 같은 함수를 다시 호출하면 전체 구조를 매우 자연스럽게 순회할 수 있습니다.
static void preorder(Node node) {
if (node == null) return;
System.out.println(node.value); // 현재 노드
preorder(node.left); // 왼쪽 서브트리
preorder(node.right); // 오른쪽 서브트리
}- 전위 / 중위 / 후위 순회
- 트리 높이 구하기
- 리프 개수 세기
- 특정 값 탐색
패턴 3. DFS
그래프나 격자에서 깊이 우선 탐색을 할 때 재귀는 매우 자주 사용됩니다. 현재 정점에서 인접 정점으로 들어가고, 그 정점에서도 다시 같은 DFS를 반복하는 구조입니다.
static void dfs(int node) {
visited[node] = true;
for (int next : graph[node]) {
if (!visited[next]) {
dfs(next);
}
}
}이 패턴에서 핵심은 종료 조건이 따로 if (n==0)처럼 보이지 않을 수 있다는 점입니다. 대신 더 이상 방문할 곳이 없을 때 자연스럽게 멈추는 구조가 종료 조건 역할을 합니다.
패턴 4. 백트래킹
백트래킹은 현재 선택을 하나 해 보고, 그 선택 아래에서 가능한 경우를 모두 재귀적으로 탐색한 뒤, 다시 선택을 되돌리는 방식입니다.
static void permutation(List<Integer> path, boolean[] used, int[] nums) {
if (path.size() == nums.length) {
System.out.println(path);
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
permutation(path, used, nums);
path.remove(path.size() - 1);
used[i] = false;
}
}여기서는 내려가면서 선택하고, 돌아오면서 원상 복구하는 흐름이 핵심입니다.
반복문과의 비교
| 관점 | 재귀 | 반복문 |
|---|---|---|
| 표현력 | 계층 구조, 분할 문제에 자연스러움 | 단순 순회와 누적에 직관적 |
| 상태 관리 | 호출 스택이 자동 관리 | 직접 변수와 스택을 관리해야 할 수 있음 |
| 메모리 | 깊은 호출 시 스택 부담 가능 | 대체로 더 예측 가능 |
| 디버깅 | 호출 흐름을 추적해야 함 | 반복 변수 흐름을 보면 됨 |
시간 복잡도와 메모리
재귀가 느리다고 느껴지는 이유는 보통 함수 호출 오버헤드 때문이 아니라, 같은 하위 문제를 너무 많이 다시 푸는 구조 때문입니다. 특히 피보나치 수열의 단순 재귀처럼 중복 호출이 많으면 시간 복잡도가 급격히 나빠질 수 있습니다.
static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}이런 형태는 재귀 자체가 문제라기보다 중복 계산이 문제입니다. 그래서 필요하면 메모이제이션이나 DP로 개선해야 합니다. 또 호출 깊이가 너무 깊어지면 스택 오버플로우 위험도 생길 수 있습니다.
자주 하는 실수
- 종료 조건이 없거나 너무 늦어서 무한 호출이 남
- 입력이 줄어들지 않아 결국 멈추지 않음
- 호출 전 작업을 해야 하는지, 호출 후 작업을 해야 하는지 순서를 잘못 잡음
- 백트래킹에서 선택 복구를 하지 않음
- 같은 하위 문제를 너무 많이 다시 호출해 시간 초과가 남
- 깊은 재귀로 스택 오버플로우가 발생함
- 현재 함수가 무엇을 반환해야 하는지 정의가 모호함
풀이 루틴
- 함수의 역할을 한 문장으로 먼저 정의한다.
- 가장 작은 입력에서 무엇을 반환할지 정한다.
- 문제를 더 작은 같은 문제로 줄이는 규칙을 정한다.
- 호출 전 / 호출 후 중 언제 작업해야 하는지 결정한다.
- 입력이 정말 줄어드는지 확인한다.
- 중복 호출이 심하면 메모이제이션이나 DP로 바꿀지 본다.
디버깅
요약
- ✅ 재귀 함수는 자기 자신을 호출하는 함수이며, 종료 조건과 재귀 단계가 반드시 필요하다.
- ✅ 재귀는 트리, DFS, 백트래킹, 분할 정복처럼 자기 닮은 꼴 구조의 문제에서 특히 강력하다.
- ✅ 호출될 때마다 함수 상태는 호출 스택에 쌓이고, 종료되면서 역순으로 돌아온다.
- ✅ 재귀의 핵심은 “문제를 더 작은 같은 문제로 줄일 수 있는가”를 보는 데 있다.
- ✅ 중복 호출이 많으면 시간 복잡도가 급격히 나빠질 수 있으므로 메모이제이션이나 DP를 함께 고려해야 한다.
- ✅ 재귀를 디버깅할 때는 전체보다 현재 호출 하나의 역할과 종료 조건부터 좁혀서 보는 것이 중요하다.