遞迴是「函式呼叫自己」的技巧。聽起來像無窮迴圈，但只要每次呼叫都讓問題變小、 並在夠小時直接給出答案，遞迴就會優雅地收斂。許多問題（樹的走訪、分治演算法、河內塔） 用遞迴表達比迭代自然得多。
學習目標
- 掌握遞迴的兩大要件：基底情況（base case）與遞迴情況（recursive case）
- 能追蹤遞迴呼叫的展開與收合過程（呼叫堆疊）
- 理解天真遞迴費氏數列的指數爆炸，會用記憶化（memoization）改善
- 看懂 K&R 的
printd與遞迴版快速排序 - 會實作河內塔、二分搜尋遞迴版
- 能分析遞迴 vs 迭代的取捨，理解堆疊溢位的風險
對照 K&R 章節
| 本單元主題 | K&R 2nd Edition |
|---|---|
| 遞迴（printd、qsort） | §4.10 Recursion |
| 快速排序（指標版） | §5.11 Pointers to Functions（qsort 骨架） |
| 二分搜尋（迭代版對照） | §3.3 Else-If |
觀念講解
1. 遞迴的思考方式
寫遞迴函式時只需要回答兩個問題：
- 基底情況：問題小到什麼程度可以直接回答？
- 遞迴情況：怎麼把問題變小一點，並假設「小問題已經解決」來組合答案？
long factorial(int n)
{
if (n <= 1) /* 基底情況：0! = 1! = 1 */
return 1;
return n * factorial(n - 1); /* 遞迴情況：n! = n * (n-1)! */
}關鍵心法：相信遞迴呼叫會給你正確答案（數學歸納法）， 不要試圖在腦中展開每一層——那是電腦的工作。
2. 呼叫堆疊的展開與收合
factorial(4) 的執行過程：
factorial(4)
= 4 * factorial(3)
= 3 * factorial(2)
= 2 * factorial(1)
= 1 <- 觸底（基底情況）
= 2 * 1 = 2 <- 開始收合
= 3 * 2 = 6
= 4 * 6 = 24每一層呼叫都在堆疊上有自己的參數與區域變數（K&R 強調：遞迴的每次呼叫 都有一份全新的自動變數）。層數太深會堆疊溢位（stack overflow）。
3. 費氏數列：天真遞迴的代價
long fib(int n) /* 直接翻譯數學定義 */
{
if (n < 2) return n;
return fib(n - 1) + fib(n - 2); /* 兩個遞迴呼叫！ */
}問題：fib(40) 會呼叫 fib(39) 和 fib(38)，而 fib(39) 又會再算一次 fib(38)……
呼叫次數呈指數成長（約 O(1.618ⁿ)）。記憶化——算過的存起來——把它降到 O(n)：
long fib_memo(int n, long memo[])
{
if (memo[n] >= 0) return memo[n]; /* 查表：算過就直接回 */
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
return memo[n];
}4. K&R printd：遞迴印整數
「先處理高位數（遞迴），再印最低位數」——順序天然正確：
void printd(int n)
{
if (n < 0) { putchar('-'); n = -n; }
if (n / 10)
printd(n / 10); /* 先把前面的位數印完 */
putchar(n % 10 + '0'); /* 再印自己這一位 */
}5. K&R 快速排序
分治法的代表作：挑一個基準（pivot），把小的搬到左邊、大的搬到右邊， 然後分別對左右兩半遞迴：
void qsort_kr(int v[], int left, int right)
{
if (left >= right) return; /* 基底：0 或 1 個元素 */
/* ...分割（partition）... */
qsort_kr(v, left, last - 1); /* 遞迴左半 */
qsort_kr(v, last + 1, right); /* 遞迴右半 */
}6. 河內塔
「把 n 層塔從 A 經 B 搬到 C」的遞迴解只有三行： 先把上面 n−1 層搬到 B，把最大盤搬到 C，再把 n−1 層從 B 搬到 C。 移動次數 2ⁿ−1——遞迴讓「不可能手寫的邏輯」變得一目瞭然。
7. 遞迴 vs 迭代
| 遞迴 | 迭代 | |
|---|---|---|
| 可讀性 | 分治/樹狀問題極佳 | 線性問題較直白 |
| 空間 | 每層呼叫占堆疊 O(深度) | 通常 O(1) |
| 速度 | 呼叫負擔；重複子問題要記憶化 | 通常較快 |
| 風險 | 堆疊溢位（深度太大） | 無 |
K&R 的提醒：遞迴通常不省時間也不省記憶體，它買到的是更精簡、更容易寫對的程式。 線性遞迴（如階乘）改寫成迴圈很容易；樹狀遞迴（如快排、樹走訪）改寫則需要自己管理堆疊， 通常不值得。
範例程式
| 檔案 | 內容 |
|---|---|
01_factorial_fib.c |
階乘（含呼叫追蹤輸出）、天真費氏 vs 記憶化費氏的呼叫次數對比、遞迴 vs 迭代 |
02_printd_qsort.c |
K&R printd（含負數處理）、K&R 快速排序完整實作、reverse 字串遞迴版 |
03_hanoi_binsearch.c |
河內塔（印出每一步）、二分搜尋遞迴版 vs 迭代版、堆疊深度觀察與溢位風險 |
編譯與執行（以第一個為例）：
cc -std=c11 -Wall -Wextra -o /tmp/demo 01_factorial_fib.c
/tmp/demo常見錯誤與陷阱
1. 忘記基底情況（或基底永遠到不了）
long bad(int n) { return n * bad(n - 1); } /* 沒有終止條件 */
long bad2(int n) { if (n == 0) return 1; return bad2(n - 2); }
/* bad2(5)：5,3,1,-1,... 跳過了 0，永遠觸不了底 */修正：基底情況要存在，且每條遞迴路徑保證會抵達（n <= 1 比 n == 1 穩健）。
2. 遞迴情況沒有讓問題變小
long stuck(int n) { if (n <= 1) return 1; return stuck(n); } /* n 沒變 */每次呼叫必須向基底情況靠近（n-1、n/2、指標前進……）。
3. 天真遞迴重複計算子問題
fib(45) 的天真版要呼叫超過 30 億次。若子問題會重複出現，
用記憶化或改寫成迭代（自底向上）。
4. 深度過大導致堆疊溢位
long sum_to(long n) { return n == 0 ? 0 : n + sum_to(n - 1); }
sum_to(100000000); /* 一億層堆疊框架 -> segfault */線性深度的遞迴要注意輸入規模；必要時改迭代。 （快排最壞情況深度 O(n)，工業級實作會限制遞迴深度並改用其他策略。）
5. 在遞迴中誤用 static/全域變數
每層呼叫共享同一個 static 變數，遞迴收合時值會互相干擾。 遞迴的狀態應該放在參數與區域變數裡。
練習題
- 寫遞迴函式
int sum_digits(int n)：回傳各位數字之和（如1234 -> 10）。 - 寫遞迴版
int my_strlen_r(const char *s)（提示：空字串是基底）。 - K&R 習題 4-12：仿
printd寫void itoa_r(int n, char s[])的遞迴版本。 - 寫
int is_palindrome(const char *s, int lo, int hi)：遞迴判斷回文。 - 寫遞迴函式
void print_binary(unsigned n)：印出 n 的二進位（提示：先遞迴 n/2 再印 n%2）。 - （進階）寫
long ackermann(int m, int n)並實測 m、n 很小時呼叫次數就爆炸的現象 （建議 m ≤ 3、n ≤ 8，並加上呼叫計數器）。
延伸閱讀
- K&R 2nd Edition，§4.10（printd、qsort）、§5.11（函式指標版 qsort）
- 《SICP》1.2 節：遞迴與迭代過程的深入辨析
- Jon Bentley,《Programming Pearls》：快速排序的工程細節
- 下一單元
09-scope-storage-classes：作用域、儲存類別與多檔案專案