要理解遞迴，你要先理解遞迴。——每個學過遞迴的人都聽過這句話，而且每次聽到都還是會笑。
先講結論
遞迴就是函數呼叫自己。它不是什麼高深的概念，但它是理解 DP、回溯、分治的基礎。你不搞懂遞迴，後面那些全部不用玩了。
記住兩件事就好：Base Case（什麼時候停） 和 每次呼叫都要往停的方向走。
遞迴長什麼樣
factorial(5)
→ 5 × factorial(4)
→ 4 × factorial(3)
→ 3 × factorial(2)
→ 2 × factorial(1)
→ 1 (Base Case!)
← 2 × 1 = 2
← 3 × 2 = 6
← 4 × 6 = 24
← 5 × 24 = 120每次呼叫都會在 call stack 上疊一層。疊太多？Stack Overflow。這就是為什麼每個遞迴都必須有 Base Case。
int factorial(int n) {
if (n <= 1) return 1; // Base Case
return n * factorial(n-1); // 往 Base Case 靠近
}三個會害死你的錯誤
// 錯誤 1：忘記 Base Case → Stack Overflow
void bad1(int n) { bad1(n - 1); }
// 錯誤 2：沒有往 Base Case 靠近 → 無窮遞迴
void bad2(int n) {
if (n == 0) return;
bad2(n); // n 根本沒變！
}
// 錯誤 3：忘記 return → 結果消失
int bad3(int n) {
if (n == 0) return 0;
bad3(n - 1); // 少了 return
}我敢說每個工程師學遞迴的時候都踩過至少一個。我全踩過。
經典問題：河內塔
把 n 個盤子從 A 移到 C，規則：一次一個，大的不能放小的上面。
這題的遞迴拆解簡直優美：
- 把上面 n-1 個從 A 移到 B（用 C 當中繼）
- 把最大的從 A 移到 C
- 把 n-1 個從 B 移到 C（用 A 當中繼）
void hanoi(int n, char from, char to, char aux) {
if (n == 1) { move(from, to); return; }
hanoi(n-1, from, aux, to);
move(from, to);
hanoi(n-1, aux, to, from);
}3 個盤子要 7 步，10 個盤子要 1023 步，64 個盤子（傳說版本）要 2^64 - 1 步。就算一秒移一個，也要 5849 億年。所以放心，世界末日還早。
遞迴 vs 迴圈
| 比較 | 遞迴 | 迴圈 |
|---|---|---|
| 可讀性 | 複雜結構更直觀 | 簡單迭代較清楚 |
| 效能 | 有函數呼叫開銷 | 較快 |
| 記憶體 | 用 Stack，可能溢出 | 固定空間 |
| 適用場景 | 樹、圖、分治 | 線性迭代 |
原則：能用迴圈寫得清楚的就用迴圈。樹的遍歷、排列組合、分治法——這些用遞迴寫才是人話。
尾遞迴：讓編譯器幫你優化
如果遞迴呼叫是函數的最後一個操作，編譯器可以把它優化成迴圈，不會爆 stack。
// 一般遞迴：return 後還要乘 n，不是尾遞迴
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n-1);
}
// 尾遞迴：return 後沒有其他操作
int factorial(int n, int acc) {
if (n <= 1) return acc;
return factorial(n-1, n * acc);
}不過要注意：Java 不支援尾遞迴優化，JavaScript 理論上支援但幾乎沒有引擎實作。所以這招在實務上不太可靠，知道概念就好。
遞迴的思考方式
我的心法是「相信遞迴」：
- 定義清楚：這個函數要做什麼？
- 找 Base Case：最小的情況是什麼？
- 假設子問題已經解決，用它來解決當前問題
- 不要去追蹤每一層的呼叫——你會瘋掉的
你不需要在腦中展開整棵遞迴樹。你只需要相信：如果 f(n-1) 能正確運作，那 f(n) 用它來算也會是對的。
數學歸納法，就是這個意思。
遞迴最像什麼？洋蔥。一層一層剝，剝到最裡面（Base Case），再一層一層把結果帶回來。如果你忘記 Base Case，那就是一顆永遠剝不完的洋蔥。