재귀: 자기 자신을 호출하는 마법

프롤로그 - "이거 무한 루프 아닌가요?"

초보 시절, 고수의 코드를 보다가 충격을 받았다. 함수 안에서 같은 함수를 호출하는 코드를 봤는데, 처음엔 버그인 줄 알았다:

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이 점점 쌓이는 걸 보면서 "이거 언제 끝나는 거야?"라는 불안감이 계속 들었다.

처음엔 뭐가 이해가 안 갔나

재귀를 처음 공부하면서 막혔던 포인트들:

1. 자기 자신을 호출하는 게 말이 돼?

함수가 자기 자신을 호출한다는 개념 자체가 직관적이지 않았다. 일반적인 프로그래밍 흐름은 "위에서 아래로, 순차적으로" 실행되는 건데, 갑자기 "자기 자신으로 돌아간다"는 게 뇌가 받아들이기 어려웠다.

2. 무한 루프 아니야?

자기 자신을 호출하면 당연히 무한 루프가 될 것 같은데, 어떻게 멈추는 건지 이해가 안 갔다. "Base Case"라는 개념을 알기 전까지는 모든 재귀 함수가 Stack Overflow로 끝날 것 같았다.

3. Base Case가 정확히 뭐야?

"종료 조건"이라고 하는데, 그게 정확히 어떤 시점에 어떻게 작동하는지 몰랐다. 특히 "왜 이 시점이 Base Case인지" 판단하는 기준이 명확하지 않았다.

4. Stack Overflow는 왜 나?

Call Stack이 뭔지도 몰랐고, 왜 재귀 함수를 잘못 짜면 "Maximum call stack size exceeded" 에러가 나는지 몰랐다. 재귀 호출 하나하나가 메모리 어딘가에 쌓인다는 걸 이해하기까지 시간이 걸렸다.

5. 무엇보다 "for문이 더 쉬운데 왜 이렇게 복잡하게?"

팩토리얼 예제를 보면 for문이 훨씬 이해하기 쉽고 빠른데, 왜 굳이 재귀로 짜는지 이해가 안 갔다. "재귀는 그냥 코드 짧게 쓰려고 쓰는 거 아니야?"라고 생각했다.

깨달음의 순간 - "마트료시카 인형, 그리고 거울"

시니어의 마트료시카 비유가 점점 와닿기 시작했다. 특히 이 설명이 결정타였다:

마트료시카 인형 (러시아 인형):

큰 인형을 열면 안에 작은 인형이 있어. 그 작은 인형을 열면 더 작은 인형이 있지. 계속 열다 보면 마지막에 더 이상 열 수 없는 제일 작은 인형이 나와.

이 제일 작은 인형이 Base Case야.

재귀도 똑같아:

• 큰 문제를 작은 문제로 쪼개고
• 작은 문제를 더 작은 문제로 쪼개고
• ...
• 가장 작은 문제(Base Case)를 풀면
• 역순으로 답이 조립되면서 전체 문제가 풀려

하지만 진짜로 이해한 순간은 "거울 양쪽에서 거울을 볼 때" 비유를 들었을 때였다.

거울 앞에 거울을 놓으면 무한히 반복되는 이미지가 보인다. 하지만 실제로는 빛의 반사 손실 때문에 어느 순간 너무 어두워서 안 보인다. 그 "안 보이는 순간"이 Base Case다.

"아, 문제를 작게 나누는 게 아니라, 문제 자체가 작은 버전의 자기 자신이구나!"

이 깨달음 이후로 재귀가 보이기 시작했다.

1. 재귀의 구조 - 필수 요소 2가지

재귀 함수는 반드시 이 두 가지를 가져야 한다:

function recursion(n) {
  // 1. Base Case (종료 조건)
  if (n === 0) {
    return "끝!";  // 더 이상 재귀 호출 없음
  }

  // 2. Recursive Case (재귀 호출)
  // 문제를 작게 만들어서 다시 자기 자신 호출
  return recursion(n - 1);
}

Base Case가 없으면?

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가 발생한다.

Recursive Case가 문제를 작게 만들지 않으면?

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가 있어도 소용없다.

2. 실제 - 팩토리얼 (Call Stack 시각화)

문제

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

Call Stack 시각화 (이게 핵심이었다)

factorial(5)를 호출하면 메모리에서 정확히 무슨 일이 일어나는가?

Step 1: 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 받음

이 시각화를 보고 나서야 재귀가 "위에서 아래로 내려가면서 쌓고, 아래에서 위로 올라오면서 계산한다"는 걸 제대로 이해했다.

3. 실제 - 폴더 탐색

제가 회사에서 만든 코드. 이게 재귀의 진가를 보여준다.

문제

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;
}

비교:

• 재귀: 10줄, 직관적, Call Stack이 자동으로 관리됨
• 반복문: 15줄, Stack을 직접 관리해야 함, 덜 직관적

결국 이거였다: 폴더 구조는 태생적으로 재귀적이다. 폴더 안에 폴더가 있고, 그 안에 또 폴더가 있는 구조. 문제 자체가 재귀적이면 재귀로 푸는 게 자연스럽다.

4. 재귀의 비밀: Call Stack

위에서 팩토리얼 예제로 Call Stack을 봤지만, 좀 더 깊이 들어가보자.

메모리에서 정확히 무슨 일이?

함수를 호출할 때마다:

1. 현재 실행 지점 저장
2. 지역 변수들 저장
3. 매개변수 저장
4. 반환 주소 저장

이 모든 게 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가 깊어지면 수천, 수만 개가 쌓이면서 메모리를 잡아먹는다.

5. Stack Overflow: 왜, 언제 터지나

발생 원인

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

실제 Stack 크기는?

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만 번 정도 호출하면 터진다.

Stack 크기를 늘릴 수 있나?

Node.js에서는 가능:

node --stack-size=10000 script.js  # Stack 크기를 10MB로 증가

하지만 근본적인 해결책은 아니다. Base Case를 제대로 설정하거나, 반복문으로 바꾸거나, Tail Call Optimization을 써야 한다.

6. 재귀 vs 반복문 - 언제 뭘 써야 하나

장단점 비교

항목	재귀	반복문
가독성	문제가 재귀적이면 직관적	단순 반복은 명확
속도	느림 (함수 호출 오버헤드)	빠름
메모리	많이 사용 (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) - 지수적으로 느려짐

메모이제이션 (Memoization) - 재귀 + 캐싱

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 ⚡⚡

결론: 피보나치는 반복문이 최고. 재귀로 푸려면 반드시 메모이제이션 써야 함.

7. 실제 - 이진 트리 탐색 (재귀가 빛나는 순간)

문제

      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 직접 관리 필요

받아들였다: 트리와 그래프 같은 재귀적 자료구조는 재귀로 푸는 게 자연스럽다. 반복문으로 억지로 푸는 건 본질을 거스르는 것 같다.

8. 꼬리 재귀 최적화 (Tail Call Optimization)

일반 재귀의 문제

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);  // ← 곱셈이 남아 있음
}

factorial(n - 1)이 반환된 후에도 n * 작업이 남아 있다. 그래서 Stack Frame을 유지해야 한다.

꼬리 재귀 (Tail Recursion)

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만 부분 지원).

Trampoline 패턴 (JS에서 TCO 흉내내기)

// 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 없이 실행됨!

작동 원리:

1. factorial은 다음 계산을 함수로 감싸서 반환 (Thunk)
2. trampoline은 반복문으로 이 함수들을 순차적으로 실행
3. Call Stack에는 항상 trampoline 하나만 쌓임

현실적으로는: 성능이 중요하면 그냥 반복문 쓰는 게 낫다. Trampoline은 학습용으로 재미있지만 프로덕션에서는 오버헤드가 있다.

9. Tower of Hanoi (하노이 탑) - 재귀의 고전

문제

     |         |         |
    |||        |         |
   |||||       |         |
  |||||||      |         |
 |||||||||     |         |
─────────  ─────────  ─────────
   A          B          C

규칙:

1. 한 번에 하나의 원판만 이동
2. 큰 원판이 작은 원판 위에 올라갈 수 없음
3. A에서 C로 모든 원판을 옮기기

핵심 통찰: n개 원판을 A에서 C로 옮기려면:

1. n-1개를 A에서 B로 옮기고 (C를 보조로)
2. 가장 큰 원판을 A에서 C로 옮기고
3. n-1개를 B에서 C로 옮긴다 (A를 보조로)

재귀 솔루션

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)

10. 실제 패턴 모음

1. 재귀적 DOM 탐색

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');

2. Deep Clone (깊은 복사)

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' (영향 없음)

3. Flatten Nested Arrays (중첩 배열 평탄화)

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]

4. Permutations (순열 생성)

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]]

5. JSON 객체 탐색

제가 실제로 회사에서 쓴 코드:

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'

11. 흔한 실수들 (내가 다 겪어본 것들)

1. Base Case를 잊어먹음

// ❌ 틀림
function countdown(n) {
  console.log(n);
  countdown(n - 1);  // 영원히 안 멈춤
}

// ✅ 올바름
function countdown(n) {
  if (n < 0) return;  // Base Case!
  console.log(n);
  countdown(n - 1);
}

2. 문제 크기를 줄이지 않음

// ❌ 틀림
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);  // 배열 줄임
}

3. 공유 상태를 mutate함

// ❌ 위험
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;
}

4. Base Case가 너무 늦음

// ❌ 비효율
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);
}

5. 재귀가 필요 없는데 재귀를 씀

// ❌ 불필요한 재귀
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);

12. 재귀 디버깅 팁

1. console.log로 depth 추적

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

2. Call Stack 시각화 (Chrome DevTools)

1. 브라우저 콘솔에서 debugger; 추가
2. 재귀 함수 실행
3. DevTools의 Call Stack 패널 확인

function factorial(n) {
  debugger;  // 여기서 멈춤
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5);

3. 최대 재귀 깊이 제한

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);
}

13. 정리 - 재귀 체크리스트

재귀 함수를 짤 때 이것만은 확인:

항목	설명	체크
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	반복문으로 더 간단하거나 빠르게 풀 수 있지 않나?	☐

14. 언제 재귀를 쓸 것인가?

재귀가 적합한 경우:

• 문제 자체가 재귀적 구조 (트리, 그래프, 중첩 구조)
• 분할 정복 (Merge Sort, Quick Sort)
• Backtracking (미로 찾기, N-Queen)
• 수학적 정의가 재귀적 (팩토리얼, 피보나치)

재귀를 피해야 하는 경우:

• 단순 반복 (0부터 n까지 합, 배열 순회)
• 재귀 깊이가 매우 깊어질 수 있는 경우
• 같은 계산을 반복하는데 메모이제이션도 안 쓸 경우
• 성능이 크리티컬한 경우

정리해본다: 문제를 보고 "이건 자기 자신의 작은 버전이네"라는 생각이 들면 재귀다. 트리는 서브트리의 모음이고, 폴더는 서브폴더의 모음이고, JSON은 JSON의 모음이다. 문제가 자기 자신과 닮았다면 재귀로 풀어라.

마치며 - "for문이 더 빠른데 왜?"

처음엔 "재귀는 느리고, 복잡하고, Stack Overflow 위험도 있는데 왜 굳이 써?"라고 생각했다. 팩토리얼도 for문이 더 빠르고, 피보나치도 반복문이 훨씬 효율적인데 말이다.

지금은 완전히 다르게 이해하게 되었다:

"재귀는 속도를 위한 게 아니라 표현력을 위한 것"

폴더 구조를 탐색할 때, 트리를 순회할 때, JSON을 파싱할 때, 이런 문제들은 태생적으로 재귀적이다. 이걸 반복문으로 풀면 Stack을 직접 관리하면서 본질을 잃는다. 재귀는 문제의 본질을 그대로 코드로 옮기는 방법이다.

마트료시카 인형이 그랬듯이, 큰 문제 안에 작은 문제가, 그 안에 더 작은 문제가 있다. 그리고 마지막 제일 작은 문제를 풀면, 마법처럼 전체가 풀린다.

결국 이거였다:

• 폴더 구조: 폴더 안의 폴더 안의 폴더...
• 트리 구조: 노드 안의 노드 안의 노드...
• JSON 객체: 객체 안의 객체 안의 객체...

"문제가 자기 자신과 닮았다면, 재귀로 풀어라. 그게 자연스럽다."