📖
재귀란
함수가 자기 자신을 호출한다
큰 문제를 같은 형태의 작은 문제로 쪼개는 방식이에요.
🌀 재귀(Recursion) = 자기 자신을 부르는 함수
재귀란 함수가 실행 도중에 자기 자신을 호출하는 것을 말해요. 하나의 큰 문제를 같은 모양의 더 작은 문제로 쪼개고, 그 작은 문제를 또 같은 방법으로 풀다 보면 결국 답에 도달해요.
💡 거울 두 개를 마주 보게 놓으면 거울 속에 거울이, 그 안에 또 거울이 끝없이 비쳐요. 러시아 인형(마트료시카)처럼 열면 똑같이 생긴 작은 인형이 계속 나오는 것도 같은 느낌이에요.
재귀
recursion
종료 조건
base case
호출 스택
팩토리얼
피보나치
분할정복
🧭
왜 배우나요? 트리 순회, 정렬(병합·퀵), DFS, 백트래킹 등 코테 단골 유형이 재귀로 생각하면 훨씬 간결해요. 지금 감을 잡아두면 다음 장(트리)부터 바로 써먹어요.
🧱
두 요소
재귀에 반드시 필요한 두 가지
이 둘이 없으면 재귀가 아니거나, 프로그램이 멈춰버려요.
제대로 된 재귀 함수에는 딱 두 가지가 반드시 있어야 해요.
🛑
① 종료 조건
base case
더 안 쪼개고 바로 답을 반환. 재귀가 멈추는 지점이에요. 예: factorial(0)=1
🔁
② 재귀 호출
recursive call
더 작은 입력으로 자기 자신을 다시 호출. 매번 종료 조건에 가까워져야 해요.
① 종료 조건 (base case)
더 이상 쪼개지 않고 바로 답을 반환하는 조건이에요. 재귀가 멈추는 지점이죠. 예를 들어 factorial(0) = 1처럼, 가장 작은 문제의 답을 직접 알려주는 부분이에요.
② 재귀 호출
더 작은 입력으로 자기 자신을 다시 부르는 부분이에요. factorial(n - 1)처럼, 매번 문제가 조금씩 작아지면서 종료 조건을 향해 다가가야 해요.
💡 재귀 호출이 매번 종료 조건에 가까워지도록 만드는 게 핵심이에요. 안 그러면 영원히 멈추지 않아요.
🔤호출 스택(call stack) — 함수를 부를 때마다 그 함수의 정보가 접시처럼 차곡차곡 쌓이는 공간이에요. factorial(3)이 factorial(2)를, 그게 또 factorial(1)을 부르면 접시가 계속 쌓이다가, 종료 조건에 닿는 순간부터 맨 위 접시부터 하나씩 정리(반환)되며 풀려요. 만약 종료 조건이 없어서 접시가 끝없이 쌓이면 결국 쌓을 공간이 바닥나는데, 이 상태를 스택 오버플로우(stack overflow)라고 해요.
⚠️
종료 조건이 없으면? 함수가 자기 자신을 무한히 호출해요(무한 재귀). 호출할 때마다 호출 스택에 쌓이는데, 스택 공간이 꽉 차면 스택 오버플로우(stack overflow) 에러가 나며 프로그램이 죽어요.
✖️
팩토리얼
n! 을 재귀로 풀어보기
가장 고전적인 재귀 예시예요.
팩토리얼은 n! = n × (n-1) × (n-2) × … × 1 이에요. 이걸 재귀로 보면 아주 깔끔해져요.
factorial(n) = n × factorial(n - 1), 그리고 종료 조건은 factorial(0) = 1 이에요.
📝 손으로 따라가기 — factorial(3)
factorial(3) = 3 × factorial(2)
= 3 × (2 × factorial(1))
= 3 × (2 × (1 × factorial(0)))
= 3 × (2 × (1 × 1)) ← 종료 조건 도달!
= 3 × 2 × 1 = 6
💡 내려갈 땐 문제를 쪼개고(factorial(0)까지), 올라올 땐 답을 곱해가며 최종 결과 6을 완성해요.
function factorial(n) {
if (n === 0) return 1; // ① 종료 조건 (base case)
return n * factorial(n - 1); // ② 더 작은 입력으로 재귀 호출
}
factorial(3); // 6
factorial(5); // 120
🔢
피보나치
두 갈래로 갈라지는 재귀
앞 두 항을 더해서 다음 항을 만드는 수열이에요.
피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, … 처럼 앞의 두 수를 더해 다음 수를 만들어요. 점화식으로 쓰면 fib(n) = fib(n-1) + fib(n-2) 이고, 종료 조건은 fib(0) = 0, fib(1) = 1 두 개예요.
function fib(n) {
if (n === 0) return 0; // 종료 조건 1
if (n === 1) return 1; // 종료 조건 2
return fib(n - 1) + fib(n - 2); // 두 번 재귀 호출
}
fib(6); // 8
🌳 호출 트리 — fib(4)
한 번 호출할 때마다 두 갈래로 갈라져요.
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
트리처럼 아래로 퍼지다가, 종료 조건(fib(0)·fib(1))에 닿으면 답이 위로 합쳐져요.
💡
단순 재귀 피보나치는 느려요. 같은 값을 중복해서 계산하기 때문에 O(2ⁿ)에 가까운 비효율이 생겨요. 나중에 메모이제이션·반복(DP)으로 개선하는 방법을 배우게 돼요. 지금은 "재귀로 이렇게 표현된다"는 형태에 집중해요.
🔤메모이제이션(memoization) — 한 번 계산한 답을 적어두었다가(메모) 다시 쓰는 기법이에요. fib(3) 같은 값을 여러 번 다시 구하는 대신, 처음 구했을 때 저장해두고 다음엔 저장값을 바로 꺼내요. "같은 계산을 두 번 하지 않는다"는 아이디어라, 느린 재귀를 확 빠르게 만들어요.
🔤DP(동적 계획법, Dynamic Programming) — 큰 문제를 작은 문제들의 답을 쌓아 올려 푸는 방법이에요. 작은 답을 한 번씩만 구해 저장해두고 재활용하기 때문에 중복 계산이 사라져요. 메모이제이션도 DP의 한 방식이고, 피보나치처럼 작은 답이 큰 답에 그대로 쓰이는 문제에 잘 맞아요.
⚖️
재귀 vs 반복
언제 재귀가 좋을까?
둘 다 같은 일을 할 수 있지만, 잘 맞는 자리가 달라요.
| 구분 | 재귀 | 반복(loop) |
|---|
| 코드 | 간결·직관적 (문제 구조 그대로) | 다소 장황할 수 있음 |
| 메모리 | 호출마다 호출 스택 사용 | 추가 스택 거의 없음 |
| 위험 | 깊으면 스택 오버플로우 | 상대적으로 안전 |
| 잘 맞는 곳 | 트리·분할정복(정렬·DFS) | 단순 순회·누적 합 |
재귀는 코드가 간결하지만 호출할 때마다 호출 스택을 쓰기 때문에 너무 깊어지면 위험해요. 대신 트리 구조나 분할정복(큰 문제를 반으로 쪼개는 방식)처럼 문제 자체가 재귀적인 모양일 땐 재귀가 훨씬 자연스러워요.
🧪
다음 장 연결. 바로 이어지는 CH 09 트리와, 이후 정렬(병합·퀵)이 재귀·분할정복으로 풀려요. 상단 🧪 실습 랩에서 factorial·fib를 직접 짜보면 감이 확 잡혀요.