LeetCode Cycle 07：Recursion、Tail Call、Stack Overflow 與何時改 iterative

Cycle 07 跟 Cycle 08 在 Notion 是合在一起的，但實作上拆開比較清楚——Cycle 07 講純遞迴（divide & conquer、tail call、stack overflow），Cycle 08 講 backtracking（剪枝、回溯狀態維護）。這篇先處理 Cycle 07。

遞迴題在面試最常踩的雷是兩個：base case 邊界沒處理乾淨、寫出指數時間的重複計算。Cycle 05 已經寫過遞迴版 reverse list，那邊主要講「stack 深度 = list 長度」。這篇正面處理上面兩個雷。

本文導覽

• 遞迴的三步驟思考
• 本文涵蓋的演算法（速覽）
• 必背題型
• Tail Call Optimization 在 JS 的真實狀況
• Stack Overflow 在 LeetCode 真實情境
• 何時轉 iterative 的判斷標準
• 面試現場 self-check
• 結語：遞迴是面試的「分解問題」訓練
• 總結表

遞迴的三步驟思考

寫遞迴函式前先答三個問題：

1. Base case 是什麼？ —— 哪個輸入可以直接回傳不用再呼叫自己
2. Recursive case 怎麼縮小？ —— 每次呼叫怎麼讓問題變小
3. 回傳什麼？ —— 子問題的結果怎麼組合成當前問題的答案

筆記裡有個小提醒「用 recursive 的加減乘除：記得 return 總和」——這個雷就是第 3 點忘了寫 return，子問題算完答案沒傳上來。

範例：1+2+...+n

// 時間複雜度：最佳 𝒪(n)，最差 𝒪(n) | 空間複雜度：𝒪(n)（call stack 深度）
function sum(n) {
  if (n === 1) return 1;          // base case
  return n + sum(n - 1);          // 縮小 + 回傳
}

• Base case：n === 1 直接回 1
• 縮小：每次 n - 1
• 組合：當前 n 加上 sum(n-1) 的結果