재귀 함수란?
함수가 자기 자신을 호출하는 것
- 장점 : 이해가 선행된다면 코드가 직관적이고 읽기 쉬운 경우가 있음
- 단점 : 함수 호출마다 스택 메모리 사용 -> 깊어지면 StackOverFlowError
재귀의 두 가지 필수 요소
| 요소 | 설명 |
|---|---|
| 1) 기저 조건 (Base Case) | 재귀를 멈추는 조건. 없거나 잘못되면 무한 루프 발생 (StackOverFlowError)⚠️ |
| 2) 재귀 호출 (Recursive Call) | 자기 자신을 더 작은 문제로 호출 |
📌 예제 1 : 팩토리얼 구하기 (5!)
5! = 5 × 4 × 3 × 2 × 1 = 120
코드
static long factorial(int n) {
if (n == 0) { // 기저 조건 : 0! = 1
return 1;
}
return n * factorial(n - 1); // 재귀 호출
}🔍 동작 방식 — factorial(5) 호출 시
재귀 함수는 크게 두 단계로 나뉜다.
1단계 : 호출 스택이 쌓이는 과정 (↓ 내려가기)
factorial(5)
└─ 5 * factorial(4)
└─ 4 * factorial(3)
└─ 3 * factorial(2)
└─ 2 * factorial(1)
└─ 1 * factorial(0)
└─ n == 0 → return 1 🛑 기저 조건 도달!2단계 : 값이 반환되는 과정 (↑ 올라오기)
return 1
return 1 * 1 = 1
return 2 * 1 = 2
return 3 * 2 = 6
return 4 * 6 = 24
return 5 * 24 = 120 🎯정답 : 120
📌 예제 2 : 피보나치 수열 구하기
피보나치 수열 : 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
규칙 : 앞의 두 수를 더하면 다음 수가 된다.
코드
static int fibRecursive(int n) {
// 기저 조건
if (n == 1 || n == 2) {
return 1; // n이 1이거나 2면 무조건 1 반환, 재귀 실행 x
}
// 재귀 호출
return fibRecursive(n - 1) + fibRecursive(n - 2);
}🔍 동작 방식 — fibRecursive(4) 호출 시
반환값은?
피보나치 수열의 4번째 값 = 3 (1, 1, 2, 3, 5 ...)
어떻게 그 값이 나오는가?
재귀 함수는 트리 아래로 내려가며 쪼개고, 위로 올라오며 합산한다.
fib(1) = 1 ← 기저조건 (바로 반환)
fib(2) = 1 ← 기저조건 (바로 반환)
fib(3) = fib(2) + fib(1) = 1 + 1 = 2
fib(4) = fib(3) + fib(2) = 2 + 1 = 31단계 : 호출 스택이 쌓이는 과정 (↓ 내려가기)
fibRecursive(4)
└─ fibRecursive(3) + fibRecursive(2)
└─ fibRecursive(2) + fibRecursive(1)
└─ n==1 또는 n==2 → return 1 🛑 기저 조건 도달!2단계 : 값이 반환되는 과정 (↑ 올라오기)
fib(1) = 1
fib(2) = 1
fib(3) = fib(2) + fib(1) = 1 + 1 = 2
fib(4) = fib(3) + fib(2) = 2 + 1 = 3 🎯호출 트리 시각화
📌 예제 3 : 하노이의 탑
문제 설명
기둥이 세 개 있음 — A, B, C
- 기둥 A에는 크기가 다른 원판이 n개 쌓여 있다.
- 모든 원판을 기둥 C로 옮겨야 한다.
규칙은 딱 두 가지:
- 한 번에 하나의 원판만 이동할 수 있다.
- 작은 원판 위에 큰 원판을 올릴 수 없다.
💡 목표: 원판이 n개일 때 최소 이동 횟수를 구하라!
🔢 예시
원판 1개 → 이동 횟수: 1
A → C (끝!)바로 C로 옮기면 됨. 기저 조건(Base Case) 에 해당
원판 2개 → 이동 횟수: 3
1. 작은 원판: A → B
2. 큰 원판: A → C
3. 작은 원판: B → C원판 3개 → 이동 횟수: 7
1. 제일 작은 원판: A → C
2. 중간 원판: A → B
3. 제일 작은 원판: C → B
4. 제일 큰 원판: A → C ← 핵심 이동!
5. 제일 작은 원판: B → A
6. 중간 원판: B → C
7. 제일 작은 원판: A → C크게 세 덩어리로 보면:
| 단계 | 설명 | 이동 횟수 |
|---|---|---|
| 1단계 | 위 2개를 임시 기둥(B)으로 이동 | 3 |
| 2단계 | 제일 큰 원판을 C로 이동 | 1 |
| 3단계 | 임시 기둥(B)의 2개를 C로 이동 | 3 |
| 합계 | 7 |
💻 코드 구현
static int hanoiCount = 0; // 이동 횟수 카운터
static void hanoi(int n, char from, char to, char temp) {
// 기저 조건: 원판이 1개면 바로 이동
if (n == 1) {
System.out.println("원판" + n + " 이동: " + from + " → " + to);
hanoiCount++;
return;
}
// 1단계: 위의 (n-1)개를 from → temp (to를 임시 공간으로)
hanoi(n - 1, from, temp, to);
// 2단계: 가장 큰 원판을 from → to
System.out.println("원판" + n + " 이동: " + from + " → " + to);
hanoiCount++;
// 3단계: temp의 (n-1)개를 temp → to (from을 임시 공간으로)
hanoi(n - 1, temp, to, from);
}📊 count++ 발생 위치 정리
기저 조건 count++ → 4번 (n=1인 hanoi 4개)
n=2 중간 count++ → 2번 (hanoi(2) 두 번의 2단계)
n=3 중간 count++ → 1번 (hanoi(3)의 2단계)
─────────────────────────
합계 → 7번
💬 마치며
재귀는 개념 자체는 단순하지만, 막상 코드를 보면 흐름을 머릿속으로 따라가기가 쉽지 않았다. 특히 하노이의 탑처럼 재귀가 여러 겹으로 쌓이는 경우엔 더 그랬다.
짝꿍이 알려준 방법대로 직접 그려보며 이해해 보려 했다. 그게 생각보다 훨씬 효과적이었다.
재귀는 익숙해질수록 점점 더 자연스럽게 읽히는 것 같다. 앞으로 문제를 더 풀면서 감각을 키워볼 생각이다.
