recursion 和 loop 分別適合什麽情景？ - paulip114/blog GitHub Wiki

雖然在大多數情況下遞迴（recursion）都可以改寫成迴圈（loop），但還是有一些**「幾乎只能用 recursion」或「用 recursion 更自然」的情境**。

---

🧠 結論：幾乎所有遞迴都能轉成迴圈，但…

• 只有在需要隱式堆疊記憶結構時（如：函式呼叫自己、需記住多層狀態）→ 用遞迴最簡單。
• 某些語言支援 Tail Call Optimization（TCO） 時，遞迴比迴圈更高效。
• 部分資料結構或問題天然是樹狀、分支結構 → 轉成迴圈會很難讀或變成超麻煩的 Stack 模擬

---

✅ 情況一：樹或圖的遍歷（DFS）

範例情境：

• 遍歷 DOM 結構
• 遞迴印出檔案系統
• 樹狀節點的搜尋或統計

function printTree(node: TreeNode) {
  console.log(node.value);
  for (const child of node.children) {
    printTree(child);
  }
}

🌀 為什麼用 recursion？
你無法預先知道有幾層巢狀（可能 2 層，也可能 100 層），用 recursion 可以天然地讓呼叫堆疊幫你記住「我現在在哪一層」。

👉 可以用 Stack 實作 DFS，但程式碼更複雜、沒這麼直觀。

---

✅ 情況二：Backtracking（回朔法）

範例情境：

• N 皇后問題
• 組合 / 排列
• 數獨解題
• 解迷宮（找所有路徑）

function solve(i: number, path: number[]) {
  if (path.length === target) {
    result.push([...path]);
    return;
  }
  for (let j = i; j < nums.length; j++) {
    path.push(nums[j]);
    solve(j + 1, path);
    path.pop(); // 回朔
  }
}

🌀 為什麼用 recursion？
因為每一次選擇都可能分成新的子問題，而每層狀態都需要被記住才能「回朔」，用 recursion + stack 很自然。

👉 如果用迴圈寫，要手動維護「狀態堆疊」，超麻煩。

---

✅ 情況三：遞迴定義的數學問題（天然遞迴）

範例情境：

• 費氏數列（Fibonacci）
• Factorial（階乘）
• 分數化簡
• 某些組合數 / 數學歸納

function factorial(n: number): number {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

👉 雖然可以用迴圈寫，但 recursion 會更貼近數學定義，更簡潔。

---

✅ 情況四：語言處理 / 編譯器 / 表達式解析

範例情境：

• 解析 (3 + (2 * 5)) → 計算器
• 處理巢狀語法（像 JSON parser）
• 解釋器、語法分析器（Parser）

// 如果是 token stream，有巢狀括號，就很適合遞迴
function parseExpression(tokens: string[]): Node {
  // 處理 ( ) 巢狀遞迴
}

👉 遞迴呼叫自己可以自然處理每一層表達式，不需自己維護巢狀堆疊。

---

❌ 哪些情況不該用 recursion？

• 太深的遞迴會爆堆疊（stack overflow）
  • 特別是你沒有 tail call 優化的語言（JS 沒支援 TCO）
  • 建議改成 loop + stack 實作（像 DFS）
• 明確知道要重複 N 次或固定結構
  • 比如跑 1000 次、陣列跑 for loop → 用迴圈就好

---

🔚 小結：什麼時候只能用（或最好用）遞迴？

情境	原因
樹狀或巢狀結構（DOM、檔案系統）	不確定深度，天然遞迴
Backtracking（N 皇后、排列）	每層選擇要記住狀態，回朔用 stack 處理麻煩
數學定義（factorial、fib）	遞迴對照數學公式，簡單清楚
語法解析（JSON、表達式）	巢狀語法遞迴下降（Recursive Descent Parser）
DFS 遍歷（進階圖論）	可用 loop + stack，但遞迴更直觀