目錄
- 什麼是遞迴？
- 遞迴的三大要素
- 遞迴的執行原理：Call Stack
- 經典遞迴範例
- 遞迴的優點
- 遞迴的缺點
- 遞迴 vs 迭代 比較表
- 如何將遞迴改成非遞迴（迭代）
- 轉換技巧總結
- 進階：尾遞迴優化
- C++ 程式碼參照
1. 什麼是遞迴？
遞迴 (Recursion) 是指一個函式直接或間接地呼叫自己的程式技巧。
直接遞迴: 間接遞迴:
void f(int n) { void A(int n) {
... ...
f(n - 1); ← 呼叫自己 B(n - 1); ← 呼叫 B
... ...
} }
void B(int n) {
...
A(n - 1); ← B 再呼叫 A
...
}
生活中的遞迴
- 俄羅斯娃娃：打開一個娃娃，裡面還有一個，直到最小的。
- 鏡中鏡：兩面鏡子對照，無限反射。
- 資料夾結構：資料夾裡面還有資料夾。
2. 遞迴的三大要素
每個正確的遞迴函式都必須具備：
要素一：Base Case（基底條件 / 終止條件）
何時停止遞迴？沒有 base case → 無窮遞迴 → Stack Overflow！
if (n == 0) return 1; // ← base case
要素二：Recursive Case（遞迴步驟）
如何把問題縮小，並呼叫自己？
return n * factorial(n - 1); // ← 問題從 n 縮小到 n-1
要素三：Progress（進展）
每次遞迴呼叫都必須朝 base case 靠近。
factorial(5) → factorial(4) → factorial(3) → ... → factorial(0) ← base case
↑ 每次 n 減少 1，必定到達 n=0
四大準則（Weiss 教科書）
- 至少一個 base case，不用遞迴就能解決。
- 每次遞迴呼叫必須朝 base case 前進。
- 假設所有遞迴呼叫都能正確運作（設計要訣）。
- 不要重複計算（複利法則）— 否則效率爆炸。
3. 遞迴的執行原理：Call Stack
每次函式呼叫，系統會在 Call Stack 上建立一個 Stack Frame，裡面存： - 參數值 - 區域變數 - 返回地址
factorial(4) 的 Call Stack 變化:
呼叫: 返回:
┌──────────────┐ ┌──────────────┐
│ factorial(0) │ ← 頂端 │ factorial(0) │ return 1
│ factorial(1) │ │ factorial(1) │ return 1*1 = 1
│ factorial(2) │ │ factorial(2) │ return 2*1 = 2
│ factorial(3) │ │ factorial(3) │ return 3*2 = 6
│ factorial(4) │ ← 底端 │ factorial(4) │ return 4*6 = 24
└──────────────┘ └──────────────┘
重點： Stack 的深度 = 遞迴的最大深度。若太深 → Stack Overflow。
4. 經典遞迴範例
4.1 階乘 (Factorial)
n! = n × (n-1)!, 0! = 1
5! = 5 × 4! = 5 × 4 × 3! = ... = 5 × 4 × 3 × 2 × 1 = 120
- 遞迴深度：O(N)
- 時間：O(N)
- 可輕易改為迭代
4.2 費氏數列 (Fibonacci)
F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)
序列: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
- 天真遞迴：O(2^N) — 大量重複計算！
- 改用迭代或 memoization：O(N)
fib(5)
/ \
fib(4) fib(3) ← fib(3) 被算了兩次！
/ \ / \
fib(3) fib(2) fib(2) fib(1) ← fib(2) 被算了三次！
/ \
fib(2) fib(1)
4.3 河內塔 (Tower of Hanoi)
將 N 個盤子從柱 A 移到柱 C（經由柱 B），規則：一次移一個，大盤不能疊在小盤上。
hanoi(n, from, to, aux):
if n == 1: 移動盤 1 from → to
else:
hanoi(n-1, from, aux, to) // 上面 n-1 個搬到 aux
移動盤 n from → to // 最大的搬到 to
hanoi(n-1, aux, to, from) // n-1 個從 aux 搬到 to
- 時間：O(2^N) — 無法改善，問題本身需要這麼多步
- 移動次數 = 2^N − 1
4.4 二元搜尋 (Binary Search)
binarySearch(arr, low, high, target):
if low > high: return -1
mid = (low + high) / 2
if arr[mid] == target: return mid
if target < arr[mid]: return binarySearch(arr, low, mid-1, target)
else: return binarySearch(arr, mid+1, high, target)
- 時間：O(log N)
- 屬於尾遞迴，可輕易改為迭代
4.5 樹的遍歷
inorder(node):
if node == NULL: return
inorder(node->left)
visit(node)
inorder(node->right)
- 遞迴深度 = 樹的高度
- 改為非遞迴需要手動模擬 Stack
4.6 快速排序 (Quick Sort)
quicksort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
quicksort(arr, low, pivot - 1)
quicksort(arr, pivot + 1, high)
- 平均 O(N log N)，最壞 O(N²)
- 改為非遞迴：用 Stack 存待排序的 (low, high) 區間
4.7 合併排序 (Merge Sort)
mergesort(arr, left, right):
if left < right:
mid = (left + right) / 2
mergesort(arr, left, mid)
mergesort(arr, mid+1, right)
merge(arr, left, mid, right)
- 時間一律 O(N log N)
- 遞迴深度 O(log N)
5. 遞迴的優點
| 優點 | 說明 |
|---|---|
| 程式碼簡潔 | 遞迴解通常比迭代解短得多（例如樹的遍歷、河內塔） |
| 自然表達 | 問題本身具有遞迴結構時（樹、圖、分治），遞迴最直觀 |
| 分治法 | Divide and Conquer 天然適合遞迴：分割 → 遞迴解 → 合併 |
| 容易證明正確性 | 可用數學歸納法證明：base case 正確 + 遞迴步驟正確 → 整體正確 |
| 回溯法 | Backtracking（如八皇后、迷宮）用遞迴最自然 |
6. 遞迴的缺點
| 缺點 | 說明 |
|---|---|
| Stack Overflow | 遞迴太深（如 N = 100000）→ 超出 Call Stack 空間 → 程式崩潰 |
| 函式呼叫開銷 | 每次呼叫需要：保存暫存器、建立 Stack Frame、跳轉，比迭代慢 |
| 重複計算 | 天真遞迴可能重複解同一子問題（如 Fibonacci → O(2^N)） |
| 空間浪費 | 每層遞迴都佔用 Stack 空間，即使很多資訊不需要保留 |
| 難以 Debug | 遞迴呼叫層層嵌套，追蹤困難 |
Stack Overflow 實例
void infinite(int n) {
infinite(n + 1); // 永遠不會結束 → Stack Overflow
}
void tooDeep(int n) {
if (n == 0) return;
tooDeep(n - 1); // n = 1000000 → Stack Overflow（一般 stack 約 1MB ~ 8MB）
}
7. 遞迴 vs 迭代 比較表
| 項目 | 遞迴 (Recursion) | 迭代 (Iteration) |
|---|---|---|
| 程式碼 | 通常較短、較直觀 | 可能較長、但更直接 |
| 速度 | 較慢（函式呼叫開銷） | 較快（直接迴圈） |
| 空間 | O(N) stack 空間（遞迴深度） | 通常 O(1)（或 O(N) 若需手動 stack） |
| Stack Overflow | 可能（深度太大） | 不會 |
| 可讀性 | 樹/圖/分治 → 遞迴更好 | 簡單迴圈 → 迭代更好 |
| 適用場景 | 分治、回溯、樹結構 | 線性掃描、簡單累加 |
原則： 能用迭代就用迭代；問題本身遞迴結構明顯時才用遞迴。
8. 如何將遞迴改成非遞迴（迭代）
方法一：直接用迴圈取代（線性遞迴）
適用於：線性遞迴（每次只有一個遞迴呼叫），如階乘、Fibonacci。
遞迴: 迭代:
int factorial(int n) { int factorial(int n) {
if (n == 0) return 1; int result = 1;
return n * factorial(n-1); for (int i = 1; i <= n; i++)
} result *= i;
return result;
}
轉換步驟： 1. 找出 base case 的值 → 設為初始值 2. 找出遞迴的方向（從 n 到 0）→ 反過來用迴圈（從 1 到 n） 3. 每次迭代做原來遞迴步驟中的運算
方法二：手動模擬 Stack（樹型遞迴）
適用於：樹的遍歷、多分支遞迴（需要保存「待辦工作」）。
遞迴 inorder: 非遞迴 inorder（手動 stack）:
void inorder(Node* n) { void inorder(Node* root) {
if (!n) return; stack<Node*> s;
inorder(n->left); Node* cur = root;
visit(n); while (cur || !s.empty()) {
inorder(n->right); while (cur) {
} s.push(cur);
cur = cur->left;
}
cur = s.top(); s.pop();
visit(cur);
cur = cur->right;
}
}
轉換步驟：
1. 建立一個 stack（模擬 Call Stack）
2. 把遞迴呼叫前要保存的狀態 push 進 stack
3. 用 while 迴圈取代遞迴：每次 pop 一個狀態來處理
4. 對每個狀態，把「需要稍後處理的子問題」push 回 stack
方法三：用 Queue/Stack 存待處理區間（分治型）
適用於：Quick Sort、Merge Sort 等分治演算法。
遞迴 quicksort: 非遞迴 quicksort:
void qs(int a[], int l, int r){ void qs(int a[], int l, int r) {
if (l >= r) return; stack<pair<int,int>> s;
int p = partition(a,l,r); s.push({l, r});
qs(a, l, p-1); while (!s.empty()) {
qs(a, p+1, r); auto [lo, hi] = s.top(); s.pop();
} if (lo >= hi) continue;
int p = partition(a, lo, hi);
s.push({lo, p-1});
s.push({p+1, hi});
}
}
方法四：Memoization（記憶化）+ 迭代（DP）
適用於：有重疊子問題的遞迴（Fibonacci、動態規劃）。
天真遞迴 O(2^N): 迭代 DP O(N):
int fib(int n) { int fib(int n) {
if (n <= 1) return n; if (n <= 1) return n;
return fib(n-1)+fib(n-2); int prev=0, curr=1;
} for (int i=2; i<=n; i++) {
int next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
方法五：Morris Traversal（不用 Stack 的樹遍歷）
利用 threaded binary tree 的概念，O(1) 空間完成 inorder 遍歷（進階技巧）。
9. 轉換技巧總結
| 遞迴類型 | 轉換方法 | 範例 |
|---|---|---|
| 線性遞迴（一個遞迴呼叫） | 直接用 for/while 迴圈 | Factorial, 線性搜尋 |
| 尾遞迴（遞迴在最後一步） | 直接用 while 迴圈 | Binary Search, GCD |
| 樹型遞迴（多個遞迴呼叫，如遍歷） | 手動模擬 Stack | Inorder, Preorder, Postorder |
| 分治型遞迴 | Stack 存待處理區間 | Quick Sort, Merge Sort |
| 重疊子問題 | Memoization 或 Bottom-up DP | Fibonacci, 背包問題 |
| 回溯型遞迴 | Stack 存狀態 + 手動回溯 | N-Queens, 迷宮 |
10. 進階：尾遞迴優化
10.1 什麼是尾遞迴 (Tail Recursion)？
遞迴呼叫是函式的最後一個動作，呼叫完後不再做任何運算。
// 尾遞迴（遞迴呼叫是最後一步，return 之後沒有其他運算）
int factorial_tail(int n, int acc) {
if (n == 0) return acc;
return factorial_tail(n - 1, n * acc); // ← 最後一步
}
// 非尾遞迴（遞迴呼叫後還要乘以 n）
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1); // ← 還要做乘法，不是尾遞迴
}
10.2 尾遞迴優化 (Tail Call Optimization, TCO)
如果編譯器支援 TCO，尾遞迴可以被自動改為迴圈，不會增加 Stack 深度！
factorial_tail(5, 1)
→ factorial_tail(4, 5) ← 重用同一個 Stack Frame
→ factorial_tail(3, 20)
→ factorial_tail(2, 60)
→ factorial_tail(1, 120)
→ factorial_tail(0, 120)
→ return 120
注意： C++ 標準不保證 TCO，但 GCC/Clang 在 -O2 以上通常會做。
10.3 如何把非尾遞迴改成尾遞迴？
技巧：加一個 accumulator 參數，把「回來後要做的運算」提前到參數裡。
// 原始（非尾遞迴）
int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1); // 回來後還要加 n
}
// 尾遞迴版
int sum_tail(int n, int acc = 0) {
if (n == 0) return acc;
return sum_tail(n - 1, acc + n); // 加 n 的動作提前到參數
}
11. C++ 程式碼參照
配套的完整 C++ 程式碼見 recursion_examples.cpp，包含：
| 編號 | 範例 | 遞迴版 | 迭代版 | 轉換方法 |
|---|---|---|---|---|
| 1 | 階乘 | factorialRec |
factorialIter |
直接迴圈 |
| 2 | 階乘（尾遞迴） | factorialTail |
— | 累加器參數 |
| 3 | Fibonacci | fibRec (O(2^N)) |
fibIter (O(N)) |
DP / 迴圈 |
| 4 | Fibonacci（Memoization） | fibMemo (O(N)) |
— | 記憶化陣列 |
| 5 | 二元搜尋 | bsRec |
bsIter |
尾遞迴 → while |
| 6 | GCD | gcdRec |
gcdIter |
尾遞迴 → while |
| 7 | 河內塔 | hanoiRec |
hanoiIter |
手動 Stack |
| 8 | 二元樹 Inorder | inorderRec |
inorderIter |
手動 Stack |
| 9 | 反轉字串 | reverseRec |
reverseIter |
雙指標 |
| 10 | Quick Sort | qsRec |
qsIter |
Stack 存區間 |
編譯方式：
g++ -std=c++11 -Wall -o recursion_examples recursion_examples.cpp
./recursion_examples