Recursion：Base Case + Smaller Problem + Call Stack

Learning outcomes

• 能辨識 base case 與 recursive case。
• 能 trace 每一層 call frame。
• 能解釋 infinite recursion / stack overflow。
• 能比較 recursion 與 iterative stack solution。

1. Factorial 只用來看結構

function factorial(n) {
  if (n <= 1) {
    return 1;
  }

  return n *
    factorial(n - 1);
}

n <= 1 是 base case；n - 1 保證問題規模朝終止方向縮小。

2. Call stack trace

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      → 1
    → 2
  → 6
→ 24

不是一次 call 在原地改 n，而是多個 function frames 同時等待內層結果。

3. Missing base case

function broken(n) {
  return broken(n + 1);
}

問題規模沒有朝終止條件前進，最終會耗盡 call stack。

4. Tree traversal 更自然

function print(node) {
  console.log(node.name);

  for (const child
       of node.children) {
    print(child);
  }
}

因為 child 本身又是同型 node，recursion 能直接映射資料結構。

5. Recursion 可以轉成 explicit stack

const stack = [root];

while (stack.length) {
  const node =
    stack.pop();

  visit(node);

  stack.push(
    ...node.children
  );
}

這把原本隱藏在 language call stack 的 pending work 改成你自己管理的 data structure。

Project checkpoint：Nested Course Tree

對 module → lesson → exercise 的 nested tree 寫 recursive traversal，計算所有 leaf exercises 數量，再改寫成 iterative stack 版本。

countExercises(node)
  base:
    exercise → 1
  recursive:
    sum children

Debug evidence：Maximum call stack size exceeded

先看 base case 是否可達、recursive input 是否真的縮小、資料是否含 cycle。Graph 有 cycle 時，單純 tree recursion 可能永遠繞圈，需要 visited set。