遞歸是「通過調用自身解決問題」的編程技巧，滿足兩個條件：重複執行過程（自我調用）與跳出條件（基例）。本文以四大經典問題為載體，展示遞歸的數學建模、代碼實現、調用樹可視化、時間空間複雜度分析，並給出迭代/動態規劃優化方向。
ReturnType recursive(Params) {
// 1. 基例：最小規模問題直接返回
if (baseCase) return baseValue;
// 2. 歸約：將問題縮小為子問題
// 3. 組合：合併子問題結果
return combine(recursive(subParams));
}
n! = n × (n-1)!，0! = 1
long factorial(int n) {
if (n <= 1) return 1; // 基例
return n * factorial(n - 1); // 歸約 + 組合
}
return factTail(n, 1) → factTail(n, acc) = n<=1? acc : factTail(n-1, n*acc)，編譯器可優化為 O(1) 空間（Java 暫不支持 TCO，需手動改迭代）。三根柱 A/B/C，n 倢盤子從小到大疊在 A 上，將所有盤子移至 C，規則：一次移一個，大盤不可壓小盤。
void hanoi(int n, char from, char aux, char to) {
if (n == 1) {
System.out.println("Move disk 1 from " + from + " to " + to);
return;
}
hanoi(n - 1, from, to, aux); // 步驟 1
System.out.println("Move disk " + n + " from " + from + " to " + to); // 步驟 2
hanoi(n - 1, aux, from, to); // 步驟 3
}
T(n) = 2T(n-1)+1 = 2^n - 1，時間 O(2^n)，空間 O(n)。n 個不同元素的所有排列，共 n! 個。
固定第 k 位，遞歸生成第 k+1..n 位的全排列，回溯時交換恢復。
void permute(int[] arr, int k) {
if (k == arr.length - 1) {
System.out.println(Arrays.toString(arr));
return;
}
for (int i = k; i < arr.length; i++) {
swap(arr, k, i);
permute(arr, k + 1);
swap(arr, k, i); // 回溯恢復
}
}
void swap(int[] a, int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; }
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
long fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2); // 大量重複計算
}
調用樹呈二叉樹，節點數 ~ φ^n，時間 O(1.618^n)，極其低效。
| 方案 | 時間 | 空間 | 核心思想 |
|---|---|---|---|
| 記憶化遞歸 | O(n) | O(n) | Map/數組緩存子問題結果 |
| 動態規劃（自底向上） | O(n) | O(1) | 滾動數組保留前兩項 |
| 矩陣快速冪 | O(log n) | O(1) | [[1,1],[1,0]]^n 矩陣乘法 |
| 通項公式 | O(1) | O(1) | Binet 公式，浮點精度限制 |
long fibDP(int n) {
if (n <= 1) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
long c = a + b;
a = b; b = c;
}
return b;
}
| 場景 | 推薦 | 理由 |
|---|---|---|
| 問題天然遞歸結構（樹、圖、分治） | 遞歸 | 代碼清晰、易證明正確性 |
| 線性遞歸、尾遞歸 | 迭代 | 避免棧溢出、常數空間 |
| 重疊子問題 | DP/記憶化 | 消除指數級重複計算 |
| 深度未知/極大 | 迭代/顯式棧 | 防 StackOverflowError |
-Xss2m 擴大或改迭代。Stream.iterate、RecursiveTask（ForkJoin）並行化分治遞歸。遞歸是「將問題縮小為同結構子問題」的思維工具。掌握基例設計、歸約關系、組合邏輯三步法，配合調用樹可視化調試，即可攻克樹遍歷、回溯搜索、分治算法等高階問題。遇到性能瓶頸，優先考慮記憶化 → DP → 數學閉式解的優化路徑。
