
재귀: 자기 자신을 호출하는 마법
마트료시카 인형 열기. 종료 조건(Base Case)이 없으면 영원히 끝나지 않는 무한 루프의 늪에 빠집니다.

마트료시카 인형 열기. 종료 조건(Base Case)이 없으면 영원히 끝나지 않는 무한 루프의 늪에 빠집니다.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

초보 시절, 고수의 코드를 보다가 충격을 받았다. 함수 안에서 같은 함수를 호출하는 코드를 봤는데, 처음엔 버그인 줄 알았다:
function search(folder) {
search(folder.subfolders); // ← 자기 자신을 호출?!
}
저: "이거 무한 루프 아닌가요? 저 함수는 영원히 끝나지 않을 텐데요..."
시니어: "Base Case 있으면 안 그래. 재귀(Recursion)야. 프로그래밍에서 가장 아름다운 개념 중 하나지."
저: "??? Base Case가 뭔데요? 그리고 왜 아름답다는 거죠?"
시니어가 책상에서 마트료시카 인형을 꺼냈다 (정말로 책상에 마트료시카 인형이 있었다). 큰 인형을 열면 작은 인형이, 그 안에 더 작은 인형이, 그 안에 또 더 작은 인형이 나왔다. 마지막 제일 작은 인형이 나오자 시니어가 말했다:
"이게 재귀야. 큰 문제를 작은 문제로 쪼개고, 작은 문제를 더 작은 문제로 쪼개고, 마지막 제일 작은 문제를 풀면 전체가 풀려."그 순간 뭔가 와닿긴 했는데, 막상 코드로 작성하려니 여전히 막막했다. 무한 루프와 재귀의 경계가 모호했고, Call Stack이 뭔지도 몰랐으며, 왜 어떤 문제는 재귀로 풀어야 하는지 이해가 안 갔다.
첫 프로젝트에서 "폴더 구조 전체를 탐색해서 특정 확장자 파일 찾기" 기능을 만들라는 업무를 받았다. 프로젝트 구조는 이랬다:
project/
├─ src/
│ ├─ components/
│ │ ├─ Button.jsx
│ │ └─ Input.jsx
│ ├─ utils/
│ │ └─ helpers.js
│ └─ pages/
│ └─ Home.jsx
└─ public/
└─ assets/
└─ logo.png
저: "음... for문으로 folder를 돌면서... 근데 subfolder가 있으면 또 for문을 돌고... 근데 그 안에 또 subfolder가 있으면... 어?"
시니어: "폴더 안에 폴더가 몇 개 depth로 있는지 모르는데 어떻게 for문으로 해? for문을 몇 번 중첩할 건데?"
저: "......"
시니어: "이런 문제가 바로 재귀가 빛을 발하는 순간이야. 폴더 구조 자체가 재귀적이거든. 폴더 안에 폴더가 있고, 그 안에 또 폴더가 있고... 문제 자체가 자기 자신과 똑같은 구조를 반복해."
그때부터 본격적으로 재귀를 공부했다.하지만 처음엔 머리가 터질 것 같았다. 코드를 따라가다 보면 함수가 자기 자신을 호출하는 순간 뇌가 멈췄고, 디버거로 따라가다 보면 Stack이 점점 쌓이는 걸 보면서 "이거 언제 끝나는 거야?"라는 불안감이 계속 들었다.
재귀를 처음 공부하면서 막혔던 포인트들:
함수가 자기 자신을 호출한다는 개념 자체가 직관적이지 않았다. 일반적인 프로그래밍 흐름은 "위에서 아래로, 순차적으로" 실행되는 건데, 갑자기 "자기 자신으로 돌아간다"는 게 뇌가 받아들이기 어려웠다.
자기 자신을 호출하면 당연히 무한 루프가 될 것 같은데, 어떻게 멈추는 건지 이해가 안 갔다. "Base Case"라는 개념을 알기 전까지는 모든 재귀 함수가 Stack Overflow로 끝날 것 같았다.
"종료 조건"이라고 하는데, 그게 정확히 어떤 시점에 어떻게 작동하는지 몰랐다. 특히 "왜 이 시점이 Base Case인지" 판단하는 기준이 명확하지 않았다.
Call Stack이 뭔지도 몰랐고, 왜 재귀 함수를 잘못 짜면 "Maximum call stack size exceeded" 에러가 나는지 몰랐다. 재귀 호출 하나하나가 메모리 어딘가에 쌓인다는 걸 이해하기까지 시간이 걸렸다.
팩토리얼 예제를 보면 for문이 훨씬 이해하기 쉽고 빠른데, 왜 굳이 재귀로 짜는지 이해가 안 갔다. "재귀는 그냥 코드 짧게 쓰려고 쓰는 거 아니야?"라고 생각했다.
시니어의 마트료시카 비유가 점점 와닿기 시작했다. 특히 이 설명이 결정타였다:
마트료시카 인형 (러시아 인형):
큰 인형을 열면 안에 작은 인형이 있어. 그 작은 인형을 열면 더 작은 인형이 있지. 계속 열다 보면 마지막에 더 이상 열 수 없는 제일 작은 인형이 나와.
이 제일 작은 인형이 Base Case야.
재귀도 똑같아:
- 큰 문제를 작은 문제로 쪼개고
- 작은 문제를 더 작은 문제로 쪼개고
- ...
- 가장 작은 문제(Base Case)를 풀면
- 역순으로 답이 조립되면서 전체 문제가 풀려
하지만 진짜로 이해한 순간은 "거울 양쪽에서 거울을 볼 때" 비유를 들었을 때였다.
거울 앞에 거울을 놓으면 무한히 반복되는 이미지가 보인다. 하지만 실제로는 빛의 반사 손실 때문에 어느 순간 너무 어두워서 안 보인다. 그 "안 보이는 순간"이 Base Case다.
"아, 문제를 작게 나누는 게 아니라, 문제 자체가 작은 버전의 자기 자신이구나!"이 깨달음 이후로 재귀가 보이기 시작했다.
재귀 함수는 반드시 이 두 가지를 가져야 한다:
function recursion(n) {
// 1. Base Case (종료 조건)
if (n === 0) {
return "끝!"; // 더 이상 재귀 호출 없음
}
// 2. Recursive Case (재귀 호출)
// 문제를 작게 만들어서 다시 자기 자신 호출
return recursion(n - 1);
}
function infiniteRecursion(n) {
// ❌ Base Case 없음!
console.log(n);
return infiniteRecursion(n - 1); // 영원히 멈추지 않음
}
infiniteRecursion(5);
// 5
// 4
// 3
// 2
// 1
// 0
// -1
// -2
// ...
// 💥 Maximum call stack size exceeded
왜 터지는가?
함수를 호출할 때마다 Call Stack에 쌓인다. Base Case가 없으면 Stack이 무한히 쌓이다가 메모리 한계에 도달하면 Overflow가 발생한다.
function badRecursion(n) {
if (n === 0) return 0; // Base Case 있음
return badRecursion(n); // ❌ n을 줄이지 않음!
}
badRecursion(5);
// 💥 Maximum call stack size exceeded
Base Case는 있지만, n이 계속 5로 유지되기 때문에 Base Case에 절대 도달하지 못한다. "진전(Progress)"이 없으면 Base Case가 있어도 소용없다.
5! = 5 × 4 × 3 × 2 × 1 = 120
function factorial(n) {
let result = 1;
for (let i = n; i > 0; i--) {
result *= i;
}
return result;
}
console.log(factorial(5)); // 120
코드: 명확하고, 빠르고, 메모리 효율적
function factorial(n) {
// Base Case: 더 이상 쪼갤 수 없는 가장 작은 문제
if (n === 0 || n === 1) {
return 1;
}
// Recursive Case: 큰 문제를 작은 문제로
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120
과정:
factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120
factorial(5)를 호출하면 메모리에서 정확히 무슨 일이 일어나는가?
┌──────────────────────┐
│ factorial(5) │ ← 현재 실행 중
│ n = 5 │
│ return 5 * ??? │ (factorial(4) 결과 대기)
└──────────────────────┘
[main]
Step 2: factorial(4) 호출
┌──────────────────────┐
│ factorial(4) │ ← 현재 실행 중
│ n = 4 │
│ return 4 * ??? │ (factorial(3) 결과 대기)
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │ (대기 중)
└──────────────────────┘
[main]
Step 3: factorial(3) 호출
┌──────────────────────┐
│ factorial(3) │ ← 현재 실행 중
│ n = 3 │
│ return 3 * ??? │
├──────────────────────┤
│ factorial(4) │
│ return 4 * ??? │
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │
└──────────────────────┘
[main]
Step 4: factorial(2) 호출
┌──────────────────────┐
│ factorial(2) │ ← 현재 실행 중
│ n = 2 │
│ return 2 * ??? │
├──────────────────────┤
│ factorial(3) │
│ return 3 * ??? │
├──────────────────────┤
│ factorial(4) │
│ return 4 * ??? │
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │
└──────────────────────┘
[main]
Step 5: factorial(1) 호출 (Base Case 도달!)
┌──────────────────────┐
│ factorial(1) │ ← 현재 실행 중
│ n = 1 │
│ return 1 │ ✅ Base Case!
├──────────────────────┤
│ factorial(2) │
│ return 2 * ??? │
├──────────────────────┤
│ factorial(3) │
│ return 3 * ??? │
├──────────────────────┤
│ factorial(4) │
│ return 4 * ??? │
├──────────────────────┤
│ factorial(5) │
│ return 5 * ??? │
└──────────────────────┘
[main]
이제 역순으로 Stack이 해제되면서 값이 계산됨:
Step 6: factorial(1) 반환
┌──────────────────────┐
│ factorial(2) │ ← 현재
│ n = 2 │
│ return 2 * 1 = 2 │ ✅
├──────────────────────┤
│ factorial(3) │
├──────────────────────┤
│ factorial(4) │
├──────────────────────┤
│ factorial(5) │
└──────────────────────┘
[main]
Step 7: factorial(2) 반환
┌──────────────────────┐
│ factorial(3) │ ← 현재
│ n = 3 │
│ return 3 * 2 = 6 │ ✅
├──────────────────────┤
│ factorial(4) │
├──────────────────────┤
│ factorial(5) │
└──────────────────────┘
[main]
Step 8: factorial(3) 반환
┌──────────────────────┐
│ factorial(4) │ ← 현재
│ n = 4 │
│ return 4 * 6 = 24 │ ✅
├──────────────────────┤
│ factorial(5) │
└──────────────────────┘
[main]
Step 9: factorial(4) 반환
┌──────────────────────┐
│ factorial(5) │ ← 현재
│ n = 5 │
│ return 5 * 24 = 120 │ ✅
└──────────────────────┘
[main]
Step 10: 최종 반환
[main] ← 120 받음
이 시각화를 보고 나서야 재귀가 "위에서 아래로 내려가면서 쌓고, 아래에서 위로 올라오면서 계산한다"는 걸 제대로 이해했다.
제가 회사에서 만든 코드. 이게 재귀의 진가를 보여준다.
project/
├─ src/
│ ├─ App.jsx
│ ├─ components/
│ │ ├─ Button.jsx
│ │ └─ Input.jsx
│ └─ utils/
│ └─ helpers.js
└─ README.md
모든 .jsx 파일을 찾아야 한다. 문제는 폴더 depth를 미리 알 수 없다는 것.
function findFiles(folder, extension) {
const results = [];
// 현재 폴더의 파일들 검사
folder.files.forEach(file => {
if (file.endsWith(extension)) {
results.push(folder.path + '/' + file);
}
});
// 🔑 재귀: 하위 폴더도 똑같이 탐색
folder.subfolders.forEach(subfolder => {
const subResults = findFiles(subfolder, extension); // 재귀 호출
results.push(...subResults);
});
return results;
}
const projectRoot = {
path: 'project',
files: ['README.md'],
subfolders: [
{
path: 'project/src',
files: ['App.jsx'],
subfolders: [
{
path: 'project/src/components',
files: ['Button.jsx', 'Input.jsx'],
subfolders: []
},
{
path: 'project/src/utils',
files: ['helpers.js'],
subfolders: []
}
]
}
]
};
const jsxFiles = findFiles(projectRoot, '.jsx');
console.log(jsxFiles);
// ['project/src/App.jsx', 'project/src/components/Button.jsx', 'project/src/components/Input.jsx']
반복문으로 하려면?
function findFilesIterative(rootFolder, extension) {
const results = [];
const stack = [rootFolder]; // Stack 자료구조 직접 구현
while (stack.length > 0) {
const folder = stack.pop();
folder.files.forEach(file => {
if (file.endsWith(extension)) {
results.push(folder.path + '/' + file);
}
});
// 하위 폴더를 Stack에 추가
folder.subfolders.forEach(subfolder => {
stack.push(subfolder);
});
}
return results;
}
비교:
결국 이거였다: 폴더 구조는 태생적으로 재귀적이다. 폴더 안에 폴더가 있고, 그 안에 또 폴더가 있는 구조. 문제 자체가 재귀적이면 재귀로 푸는 게 자연스럽다.
위에서 팩토리얼 예제로 Call Stack을 봤지만, 좀 더 깊이 들어가보자.
함수를 호출할 때마다:
이 모든 게 Stack Frame이라는 단위로 Call Stack에 쌓인다.
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(3);
메모리 상태:
Heap (동적 메모리)
┌─────────────────┐
│ (비어 있음) │
└─────────────────┘
Call Stack
┌─────────────────┐
│ factorial(1) │ ← Top (현재 실행 중)
│ n=1, return=1 │
├─────────────────┤
│ factorial(2) │
│ n=2, return=?? │ (factorial(1) 결과 대기)
├─────────────────┤
│ factorial(3) │
│ n=3, return=?? │ (factorial(2) 결과 대기)
├─────────────────┤
│ main() │
└─────────────────┘
각 Stack Frame의 크기는 작지만 (수백 바이트), 재귀 depth가 깊어지면 수천, 수만 개가 쌓이면서 메모리를 잡아먹는다.
function badRecursion(n) {
console.log(n);
return badRecursion(n - 1); // Base Case 없음!
}
badRecursion(5);
Call Stack:
[badRecursion(-99999)]
[badRecursion(-99998)]
...
[badRecursion(0)]
[badRecursion(1)]
[badRecursion(2)]
[badRecursion(3)]
[badRecursion(4)]
[badRecursion(5)]
[main]
↓ 계속 쌓임
💥 Maximum call stack size exceeded
let count = 0;
function testStack() {
count++;
testStack();
}
try {
testStack();
} catch (e) {
console.log(`Maximum: ${count} calls`);
}
// Node.js: ~12,000 calls
// Chrome: ~10,000 calls
// Firefox: ~50,000 calls
브라우저/환경마다 다르지만, 보통 1만~5만 번 정도 호출하면 터진다.
Node.js에서는 가능:
node --stack-size=10000 script.js # Stack 크기를 10MB로 증가
하지만 근본적인 해결책은 아니다. Base Case를 제대로 설정하거나, 반복문으로 바꾸거나, Tail Call Optimization을 써야 한다.
| 항목 | 재귀 | 반복문 |
|---|---|---|
| 가독성 | 문제가 재귀적이면 직관적 | 단순 반복은 명확 |
| 속도 | 느림 (함수 호출 오버헤드) | 빠름 |
| 메모리 | 많이 사용 (Call Stack) | 적게 사용 |
| 디버깅 | 어려움 (Stack trace 복잡) | 쉬움 |
| 코드 길이 | 짧고 우아함 | 길고 장황할 수 있음 |
| 적합한 문제 | 트리, 그래프, 분할 정복 | 단순 반복, 카운팅 |
| 부적합한 문제 | 단순 반복, 큰 n | 트리 탐색 (코드 복잡) |
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
console.time('fib(40)');
console.log(fib(40)); // 102334155
console.timeEnd('fib(40)');
// fib(40): 약 1.5초 😱
문제: 같은 계산을 엄청나게 반복함
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ │ ├─ fib(2) ← 계산됨
│ │ │ ├─ fib(1)
│ │ │ └─ fib(0)
│ │ └─ fib(1)
│ └─ fib(2) ← 또 계산됨 (중복!)
│ ├─ fib(1)
│ └─ fib(0)
└─ fib(3) ← 또또 계산됨 (중복!)
├─ fib(2)
│ ├─ fib(1)
│ └─ fib(0)
└─ fib(1)
fib(40)을 계산하면 fib(2)가 무려 63,245,986번 호출된다!
시간 복잡도: O(2^n) - 지수적으로 느려짐
function fib(n, memo = {}) {
// 이미 계산한 값이면 캐시에서 반환
if (n in memo) return memo[n];
// Base Case
if (n <= 1) return n;
// 계산 후 캐시에 저장
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
console.time('fib(40) with memo');
console.log(fib(40)); // 102334155
console.timeEnd('fib(40) with memo');
// fib(40) with memo: 약 0.5ms ⚡
3000배 빨라졌다!
시간 복잡도: O(n)
function fib(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
console.time('fib(40) iterative');
console.log(fib(40)); // 102334155
console.timeEnd('fib(40) iterative');
// fib(40) iterative: 약 0.01ms ⚡⚡
결론: 피보나치는 반복문이 최고. 재귀로 푸려면 반드시 메모이제이션 써야 함.
10
/ \
5 15
/ \ / \
3 7 12 20
모든 노드를 출력하고 싶다 (DFS - Depth First Search).
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
function traverse(node) {
if (!node) return; // Base Case: null 노드 도달
console.log(node.value); // 현재 노드 출력
traverse(node.left); // 왼쪽 서브트리 재귀 탐색
traverse(node.right); // 오른쪽 서브트리 재귀 탐색
}
// 트리 구성
const root = new Node(10,
new Node(5,
new Node(3),
new Node(7)
),
new Node(15,
new Node(12),
new Node(20)
)
);
traverse(root);
// 출력: 10, 5, 3, 7, 15, 12, 20 (Pre-order traversal)
아름답게 짧다: 6줄
function traverseIterative(root) {
if (!root) return;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
console.log(node.value);
// 오른쪽을 먼저 push (Stack은 LIFO라서)
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
}
traverseIterative(root);
// 출력: 10, 5, 3, 7, 15, 12, 20
코드 길이: 14줄, Stack 직접 관리 필요
받아들였다: 트리와 그래프 같은 재귀적 자료구조는 재귀로 푸는 게 자연스럽다. 반복문으로 억지로 푸는 건 본질을 거스르는 것 같다.
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1); // ← 곱셈이 남아 있음
}
factorial(n - 1)이 반환된 후에도 n * 작업이 남아 있다. 그래서 Stack Frame을 유지해야 한다.
function factorial(n, acc = 1) {
if (n === 1) return acc;
return factorial(n - 1, n * acc); // ← 바로 반환 (추가 작업 없음)
}
factorial(5, 1);
과정:
factorial(5, 1)
→ factorial(4, 5)
→ factorial(3, 20)
→ factorial(2, 60)
→ factorial(1, 120)
→ 120
재귀 호출이 함수의 마지막 작업이다. 이론적으로 컴파일러가 이를 감지하면 Stack을 재사용해서 반복문처럼 최적화할 수 있다.
하지만 JavaScript의 현실: ES6부터 Tail Call Optimization (TCO)이 명세에 포함됐지만, 대부분의 JS 엔진이 구현하지 않았다 (Safari만 부분 지원).
// Thunk를 반환하는 버전
function factorial(n, acc = 1) {
if (n === 1) return acc;
return () => factorial(n - 1, n * acc); // 함수를 반환
}
// Trampoline: 함수면 계속 실행, 값이면 반환
function trampoline(fn) {
while (typeof fn === 'function') {
fn = fn();
}
return fn;
}
console.log(trampoline(factorial(100000, 1)));
// Stack Overflow 없이 실행됨!
작동 원리:
factorial은 다음 계산을 함수로 감싸서 반환 (Thunk)trampoline은 반복문으로 이 함수들을 순차적으로 실행trampoline 하나만 쌓임현실적으로는: 성능이 중요하면 그냥 반복문 쓰는 게 낫다. Trampoline은 학습용으로 재미있지만 프로덕션에서는 오버헤드가 있다.
| | |
||| | |
||||| | |
||||||| | |
||||||||| | |
───────── ───────── ─────────
A B C
규칙:
핵심 통찰: n개 원판을 A에서 C로 옮기려면:
function hanoi(n, from, to, aux) {
if (n === 1) {
console.log(`Move disk 1 from ${from} to ${to}`);
return;
}
// Step 1: n-1개를 from에서 aux로 (to를 보조로)
hanoi(n - 1, from, aux, to);
// Step 2: 가장 큰 원판을 from에서 to로
console.log(`Move disk ${n} from ${from} to ${to}`);
// Step 3: n-1개를 aux에서 to로 (from을 보조로)
hanoi(n - 1, aux, to, from);
}
hanoi(3, 'A', 'C', 'B');
출력:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
시각화 (3개 원판):
초기 상태:
A B C
|||
|||||
───── ───── ─────
Move disk 1 from A to C:
A B C
|||
|||||
───── ───── ─────
Move disk 2 from A to B:
A B C
||||| |||
───── ───── ─────
Move disk 1 from C to B:
A B C
|||
|||||
───── ───── ─────
Move disk 3 from A to C:
A B C
||| |||||
|||||
───── ───── ─────
(계속...)
이 문제를 반복문으로? 거의 불가능. 재귀가 유일한 직관적인 해법이다.
시간 복잡도: O(2^n) - 느리지만 피할 수 없음 (최소 이동 횟수가 2^n - 1)
function findElementById(node, id) {
// Base Case: 찾았거나, 노드가 없음
if (!node) return null;
if (node.id === id) return node;
// 모든 자식 노드에 대해 재귀
for (let child of node.children) {
const found = findElementById(child, id);
if (found) return found;
}
return null;
}
const element = findElementById(document.body, 'my-button');
function deepClone(obj) {
// Base Case: primitive 타입
if (obj === null || typeof obj !== 'object') {
return obj;
}
// Array
if (Array.isArray(obj)) {
return obj.map(item => deepClone(item));
}
// Object
const cloned = {};
for (let key in obj) {
cloned[key] = deepClone(obj[key]); // 재귀
}
return cloned;
}
const original = {
name: 'John',
address: {
city: 'Seoul',
nested: {
deep: 'value'
}
},
hobbies: ['coding', ['nested', 'array']]
};
const copied = deepClone(original);
copied.address.city = 'Busan';
console.log(original.address.city); // 'Seoul' (영향 없음)
function flatten(arr) {
const result = [];
for (let item of arr) {
if (Array.isArray(item)) {
result.push(...flatten(item)); // 재귀
} else {
result.push(item);
}
}
return result;
}
const nested = [1, [2, [3, [4, 5]], 6], 7];
console.log(flatten(nested));
// [1, 2, 3, 4, 5, 6, 7]
function permute(arr) {
const result = [];
// Base Case: 빈 배열 또는 1개
if (arr.length <= 1) return [arr];
for (let i = 0; i < arr.length; i++) {
const current = arr[i];
const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
const perms = permute(remaining); // 재귀
for (let perm of perms) {
result.push([current, ...perm]);
}
}
return result;
}
console.log(permute([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
제가 실제로 회사에서 쓴 코드:
const config = {
app: {
name: "MyApp",
settings: {
theme: "dark",
lang: "ko",
advanced: {
debug: true
}
}
},
db: {
host: "localhost",
port: 5432
}
};
// 모든 leaf 값 찾기
function findValues(obj, result = []) {
for (let key in obj) {
const value = obj[key];
if (typeof value === 'object' && value !== null) {
findValues(value, result); // 재귀
} else {
result.push(value);
}
}
return result;
}
console.log(findValues(config));
// ['MyApp', 'dark', 'ko', true, 'localhost', 5432]
// 특정 키 찾기 (중첩된 객체에서)
function findKey(obj, targetKey) {
if (targetKey in obj) {
return obj[targetKey];
}
for (let key in obj) {
if (typeof obj[key] === 'object' && obj[key] !== null) {
const found = findKey(obj[key], targetKey);
if (found !== undefined) return found;
}
}
return undefined;
}
console.log(findKey(config, 'debug')); // true
console.log(findKey(config, 'theme')); // 'dark'
// ❌ 틀림
function countdown(n) {
console.log(n);
countdown(n - 1); // 영원히 안 멈춤
}
// ✅ 올바름
function countdown(n) {
if (n < 0) return; // Base Case!
console.log(n);
countdown(n - 1);
}
// ❌ 틀림
function search(arr, target) {
if (arr[0] === target) return true;
return search(arr, target); // arr이 그대로!
}
// ✅ 올바름
function search(arr, target) {
if (arr.length === 0) return false;
if (arr[0] === target) return true;
return search(arr.slice(1), target); // 배열 줄임
}
// ❌ 위험
const result = [];
function traverse(node) {
if (!node) return;
result.push(node.value); // 전역 변수 mutate
traverse(node.left);
traverse(node.right);
}
// ✅ 안전
function traverse(node, result = []) {
if (!node) return result;
result.push(node.value);
traverse(node.left, result);
traverse(node.right, result);
return result;
}
// ❌ 비효율
function fib(n) {
if (n === 0) return 0;
if (n === 1) return 1;
return fib(n - 1) + fib(n - 2);
}
// fib(-5)를 호출하면? 무한 루프!
// ✅ 방어적
function fib(n) {
if (n < 0) throw new Error('Negative input');
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// ❌ 불필요한 재귀
function sum(arr, index = 0) {
if (index === arr.length) return 0;
return arr[index] + sum(arr, index + 1);
}
// ✅ 그냥 반복문 써라
function sum(arr) {
let total = 0;
for (let num of arr) total += num;
return total;
}
// 또는 reduce
const sum = arr => arr.reduce((a, b) => a + b, 0);
function factorial(n, depth = 0) {
const indent = ' '.repeat(depth);
console.log(`${indent}factorial(${n}) called`);
if (n === 1) {
console.log(`${indent}→ Base Case! Return 1`);
return 1;
}
const result = n * factorial(n - 1, depth + 1);
console.log(`${indent}→ Return ${n} * ${result / n} = ${result}`);
return result;
}
factorial(5);
출력:
factorial(5) called
factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
→ Base Case! Return 1
→ Return 2 * 1 = 2
→ Return 3 * 2 = 6
→ Return 4 * 6 = 24
→ Return 5 * 24 = 120
debugger; 추가function factorial(n) {
debugger; // 여기서 멈춤
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5);
function safeFib(n, maxDepth = 100, depth = 0) {
if (depth > maxDepth) {
throw new Error(`Max recursion depth ${maxDepth} exceeded`);
}
if (n <= 1) return n;
return safeFib(n - 1, maxDepth, depth + 1) +
safeFib(n - 2, maxDepth, depth + 1);
}
재귀 함수를 짤 때 이것만은 확인:
| 항목 | 설명 | 체크 |
|---|---|---|
| Base Case | 재귀 호출 없이 바로 반환하는 경우가 있나? | ☐ |
| Progress | 매 호출마다 문제가 작아지나? Base Case에 가까워지나? | ☐ |
| Correctness | Base Case와 Recursive Case 모두 올바른 값을 반환하나? | ☐ |
| Termination | 모든 입력에 대해 언젠가는 Base Case에 도달하나? | ☐ |
| Edge Cases | n=0, n=1, negative, null, empty array 등 처리했나? | ☐ |
| Performance | 같은 계산 반복하지 않나? 메모이제이션 필요한가? | ☐ |
| Stack Overflow | 재귀 깊이가 너무 깊어질 가능성은 없나? | ☐ |
| Alternative | 반복문으로 더 간단하거나 빠르게 풀 수 있지 않나? | ☐ |
재귀가 적합한 경우:
재귀를 피해야 하는 경우:
정리해본다: 문제를 보고 "이건 자기 자신의 작은 버전이네"라는 생각이 들면 재귀다. 트리는 서브트리의 모음이고, 폴더는 서브폴더의 모음이고, JSON은 JSON의 모음이다. 문제가 자기 자신과 닮았다면 재귀로 풀어라.
처음엔 "재귀는 느리고, 복잡하고, Stack Overflow 위험도 있는데 왜 굳이 써?"라고 생각했다. 팩토리얼도 for문이 더 빠르고, 피보나치도 반복문이 훨씬 효율적인데 말이다.
지금은 완전히 다르게 이해하게 되었다:
"재귀는 속도를 위한 게 아니라 표현력을 위한 것"폴더 구조를 탐색할 때, 트리를 순회할 때, JSON을 파싱할 때, 이런 문제들은 태생적으로 재귀적이다. 이걸 반복문으로 풀면 Stack을 직접 관리하면서 본질을 잃는다. 재귀는 문제의 본질을 그대로 코드로 옮기는 방법이다.
마트료시카 인형이 그랬듯이, 큰 문제 안에 작은 문제가, 그 안에 더 작은 문제가 있다. 그리고 마지막 제일 작은 문제를 풀면, 마법처럼 전체가 풀린다.
결국 이거였다: