本檔收錄本單元的練習題、完整解題思路與參考解答。
強烈建議先自己動手做：看完題目就闔上這份檔案，寫出你的版本、編譯、執行、卡住了再回來看「解題思路」；
真的做完了，再對照「參考解答」與「程式碼講解」。每題的完整程式碼也放在 exercises/ 資料夾，可直接編譯：
cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_sum_digits.c && /tmp/out練習 1：sum_digits —— 各位數字之和（難度：基礎）
題目
寫遞迴函式 int sum_digits(int n)：回傳 n 的各位數字之和
（如 1234 → 1+2+3+4 = 10）。負數視同其絕對值（-256 → 13）。
測試：多位數、0、一位數、負數、含很多 0 的數。
解題思路
- 照本單元的心法回答兩個問題：
- 基底情況：什麼時候可以直接回答？——
n只有一位數（n < 10）時， 數字和就是n自己。 - 遞迴情況：怎麼把問題變小？——把n拆成「最後一位」與「其餘部分」：n % 10是最後一位、n / 10是去掉最後一位的較小數字。 於是sum_digits(n) = n % 10 + sum_digits(n / 10)。 - 展開驗證（相信遞迴之前先手算一次建立信心）：
sum_digits(1234)
= 4 + sum_digits(123)
= 4 + (3 + sum_digits(12))
= 4 + (3 + (2 + sum_digits(1))) <- 1 < 10 觸底，回 1
= 4 + 3 + 2 + 1 = 10- 負數處理：進函式先
if (n < 0) n = -n;正規化。 注意這行只在最外層呼叫真正生效（之後 n/10 不會再變負）， 放在函式開頭簡單又不影響正確性。 - 每條路徑都會觸底嗎？
n / 10每次至少去掉一位， 位數有限 → 必然在有限步內< 10。遞迴的「終止證明」就這麼一句。
參考解答
/*
* ex1_sum_digits.c
* ----------------
* 練習 1：sum_digits —— 遞迴計算各位數字之和（難度：基礎）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_sum_digits.c
* 執行：/tmp/out
*/
#include <stdio.h>
/*
* 遞迴定義：
* 基底：n 只有一位數（0..9）-> 和就是 n 自己
* 遞迴：sum_digits(n) = (n 的最後一位) + sum_digits(去掉最後一位的 n)
* = n % 10 + sum_digits(n / 10)
* 負數：先轉成正數處理（-1234 的數字和視為 10）。
*/
int sum_digits(int n)
{
if (n < 0)
n = -n; /* 負數正規化，只做一次 */
if (n < 10) /* 基底情況：一位數 */
return n;
return n % 10 + sum_digits(n / 10); /* 遞迴情況 */
}
int main(void)
{
int tests[] = { 1234, 0, 7, 99999, -256, 1000000 };
int n = (int)(sizeof tests / sizeof tests[0]);
for (int i = 0; i < n; i++)
printf("sum_digits(%d) = %d\n", tests[i], sum_digits(tests[i]));
/* 手動展開一次，對照理解：
* sum_digits(1234)
* = 4 + sum_digits(123)
* = 4 + (3 + sum_digits(12))
* = 4 + (3 + (2 + sum_digits(1)))
* = 4 + 3 + 2 + 1 = 10 */
printf("\n驗算：1+2+3+4 = %d\n", 1 + 2 + 3 + 4);
return 0;
}程式碼講解
- 基底寫
n < 10而不是n == 0：兩種都能寫對，但n < 10少一層呼叫， 且「一位數的數字和是自己」語意更直接。 （若用n == 0當基底回 0，遞迴式不變也正確——殊途同歸。） n % 10與n / 10是「拆數字」的黃金搭檔：取尾巴、去尾巴。 之後的 itoa、print_binary 都是同一組工具。sum_digits(0)直接落在基底回 0——不需特判。- 易錯處：極端值
INT_MIN取-n會溢位（其絕對值超出 int 範圍）； 測試資料刻意避開，嚴格處理需在 long 域先轉換（練習 3 會示範）。
範例輸出
sum_digits(1234) = 10
sum_digits(0) = 0
sum_digits(7) = 7
sum_digits(99999) = 45
sum_digits(-256) = 13
sum_digits(1000000) = 1
驗算：1+2+3+4 = 10練習 2：my_strlen_r —— 遞迴版字串長度（難度：基礎）
題目
寫遞迴版 int my_strlen_r(const char *s)（提示：空字串是基底）。
測試一般字串、空字串、單一字元。
解題思路
- 基底情況：空字串（
*s == '\0'）的長度是 0——題目的提示就是答案的一半。 - 遞迴情況：一個非空字串的長度 = 1（開頭這個字元）+ 剩下部分的長度。
「剩下部分」用指標算術表達：
s + 1（從下一個字元開始的字串）。 - 展開看一次：
my_strlen_r("abc")
= 1 + my_strlen_r("bc")
= 1 + (1 + my_strlen_r("c"))
= 1 + (1 + (1 + my_strlen_r(""))) <- 空字串觸底，回 0
= 3- 為什麼會終止？ 每層呼叫
s + 1向'\0'前進一格，字串有限長 → 必觸底。 - 與迭代版的對照：第 02 單元的指標版 strlen 是迴圈 + 指標相減； 遞迴版把「前進」變成「縮小問題」。長度 n 的字串要疊 n 層呼叫框架—— 對超長字串有堆疊溢位風險，這是「線性遞迴改迭代很容易、通常也值得」的例證 （K&R 的提醒）。
參考解答
/*
* ex2_strlen_r.c
* --------------
* 練習 2：my_strlen_r —— 遞迴版字串長度（難度：基礎）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_strlen_r.c
* 執行：/tmp/out
*/
#include <stdio.h>
/*
* 遞迴定義：
* 基底：空字串（*s == '\0'）長度為 0
* 遞迴：長度 = 1（目前這個字元）+ 剩下部分的長度（s+1 開始）
*
* my_strlen_r("abc")
* = 1 + my_strlen_r("bc")
* = 1 + (1 + my_strlen_r("c"))
* = 1 + (1 + (1 + my_strlen_r(""))) <- 觸底回 0
* = 3
*/
int my_strlen_r(const char *s)
{
if (*s == '\0') /* 基底情況：空字串 */
return 0;
return 1 + my_strlen_r(s + 1); /* 遞迴：指標前進一格，問題變小 */
}
int main(void)
{
const char *tests[] = { "hello", "", "a", "recursion is elegant" };
int n = (int)(sizeof tests / sizeof tests[0]);
for (int i = 0; i < n; i++)
printf("my_strlen_r(\"%s\") = %d\n", tests[i], my_strlen_r(tests[i]));
return 0;
}程式碼講解
s + 1不是「字元加一」而是「指標前進一格」——遞迴的「變小」發生在指標上。 傳s + 1不會影響呼叫端（指標本來就是傳值）。- 整個函式兩行：基底 + 遞迴。遞迴的表達力在「定義即程式」—— 函式的長相和數學定義一模一樣。
"recursion is elegant"有 20 個字元 → 21 層呼叫（含空字串那層）。 現代機器的預設堆疊（8MB）撐得起數十萬層，日常字串毫無問題； 但拿它去量 100MB 的緩衝區就會 segfault——尾遞迴不保證被最佳化，別賭。- 易錯處：基底忘了寫、或遞迴時傳
s（沒前進）——無窮遞迴，堆疊溢位。
範例輸出
my_strlen_r("hello") = 5
my_strlen_r("") = 0
my_strlen_r("a") = 1
my_strlen_r("recursion is elegant") = 20練習 3：itoa_r —— 遞迴版整數轉字串（難度：進階）
題目
（K&R 習題 4-12）仿照 printd 的想法，寫遞迴版 void itoa_r(int n, char s[])：
把整數轉成字串。要求能處理 0、負數、以及 INT_MAX / INT_MIN 兩個極端值。
解題思路
- printd 的洞見：印 1234 要先印 123 再印 4——
「先遞迴處理高位、返回後再處理自己這一位」，順序自然正確、不需反轉。
本題只是把
putchar換成「寫進陣列」。 - 寫進陣列的新問題：位置。
putchar不用管位置，寫陣列要知道「寫到哪了」。 兩個選項： - static 索引——壞主意：單元講義明說遞迴中的 static 會互相干擾且不可重入； - 把索引當參數傳、當回傳值還——int itoa_helper(long n, char s[], int i)： 收到「從哪開始寫」，回傳「下一個可寫位置」。純函數式，乾淨可重入。 - 結構：外層
itoa_r處理負號與收尾'\0'，內層itoa_helper只管無號的位數：
itoa_r(-42)：
s[0] = '-'，i = 1，v = 42
itoa_helper(42, s, 1)
42 >= 10 -> i = itoa_helper(4, s, 1) （先寫高位）
4 < 10：s[1]='4'，回 2
s[2] = '2'，回 3
s[3] = '\0' -> "-42"- INT_MIN 陷阱（K&R 原題的重點）：
-INT_MIN溢位！INT_MIN = -2147483648的絕對值超出 int 範圍。 解法：先把 n 放進 long（macOS 上 64 位元）再取負——long v = n; v = -v;在 long 域中安全。
參考解答
/*
* ex3_itoa_r.c
* ------------
* 練習 3：itoa_r —— 仿 K&R printd 的遞迴版 itoa（難度：進階）
* 出處：K&R 習題 4-12
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_itoa_r.c
* 執行：/tmp/out
*/
#include <stdio.h>
#include <limits.h>
/*
* 內部遞迴：把 |n| 的各位數字依序附加到 s 尾端。
* 用「目前寫到的索引」當參數傳遞與回傳，避免 static 狀態。
* printd 的洞見：先遞迴處理高位數，回來再寫自己這一位——順序天然正確。
*/
static int itoa_helper(long n, char s[], int i)
{
if (n >= 10)
i = itoa_helper(n / 10, s, i); /* 先寫完前面的位數 */
s[i++] = (char)(n % 10 + '0'); /* 再寫最低位 */
return i; /* 回傳下一個可寫位置 */
}
/*
* 對外介面：處理負號，最後補 '\0'。
* 用 long 暫存避免 -INT_MIN 溢位（INT_MIN 的絕對值超出 int 範圍）。
*/
void itoa_r(int n, char s[])
{
long v = n;
int i = 0;
if (v < 0) {
s[i++] = '-';
v = -v; /* long 域中安全取絕對值 */
}
i = itoa_helper(v, s, i);
s[i] = '\0';
}
int main(void)
{
int tests[] = { 12345, 0, 7, -42, -9876, INT_MAX, INT_MIN };
int n = (int)(sizeof tests / sizeof tests[0]);
char buf[32];
for (int i = 0; i < n; i++) {
itoa_r(tests[i], buf);
printf("itoa_r(%11d) -> \"%s\"\n", tests[i], buf);
}
return 0;
}程式碼講解
itoa_helper的遞迴條件n >= 10：與 printd 的if (n / 10)等價—— 「還有更高位就先處理」。一位數直接落到寫入行，就是基底。- 索引「傳進去、還回來」的鏈：每層寫一個字元、索引 +1，
返回鏈把最終位置一路傳回外層，外層在那裡補
'\0'。 沒有任何共享狀態——同一時間多處呼叫也不會互踩（可重入）。 - 輸出驗證
INT_MIN → "-2147483648"：這正是天真寫法 （if (n < 0) n = -n;在 int 域）會壞掉的輸入—— 溢位是未定義行為，可能印出 "-(-2147483648)" 之類的怪東西或直接錯。 (char)(n % 10 + '0')：數位轉字元（'0'..'9'連續保證），轉型消警告。- 對照迭代版 itoa（K&R §3.6 是「先反著寫再 reverse」）： 遞迴版免去 reverse，優雅展示了「呼叫堆疊就是天然的反轉器」。
範例輸出
itoa_r( 12345) -> "12345"
itoa_r( 0) -> "0"
itoa_r( 7) -> "7"
itoa_r( -42) -> "-42"
itoa_r( -9876) -> "-9876"
itoa_r( 2147483647) -> "2147483647"
itoa_r(-2147483648) -> "-2147483648"練習 4：is_palindrome —— 遞迴判斷回文（難度：進階）
題目
寫函式 int is_palindrome(const char *s, int lo, int hi)：
遞迴判斷 s[lo..hi]（含兩端）是否為回文。
測試：奇數長度回文、偶數長度回文、非回文、單一字元、空字串、
「首尾相同但內層不同」（如 "abca"）。
解題思路
- 回文的遞迴定義（把定義寫出來，程式就出來了）： 一個字串是回文 ⟺ 頭尾字元相同，且去掉頭尾後剩下的部分也是回文。
- 兩個基底 + 一個遞迴：
- 基底 1（成功觸底）：
lo >= hi——區間剩 0 個（偶數長度收斂）或 1 個字元（奇數長度收斂），天然是回文 → 回 1； - 基底 2（提前失敗）：s[lo] != s[hi]→ 回 0，不必再看內層； - 遞迴：頭尾相同 → 答案交給is_palindrome(s, lo + 1, hi - 1)。 - 收斂圖：
is_palindrome("level", 0, 4)
l == l ✓ -> is_palindrome("level", 1, 3)
e == e ✓ -> is_palindrome("level", 2, 2)
lo == hi 觸底 -> 1本質上就是第 02 單元「頭尾雙指標」的遞迴版——
迭代版用 lo++, hi-- 的迴圈，遞迴版用參數縮小區間，一體兩面。
4. 介面包裝：(lo, hi) 介面靈活但難用，再包一層
is_palindrome_str(s) 自動算 hi = strlen(s) - 1。
注意空字串時 hi = -1，lo(0) >= hi(-1) 直接觸底回 1——邊界自動正確。
參考解答
/*
* ex4_palindrome.c
* ----------------
* 練習 4：is_palindrome —— 遞迴判斷回文（難度：進階）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_palindrome.c
* 執行：/tmp/out
*/
#include <stdio.h>
#include <string.h>
/*
* 判斷 s[lo..hi]（含兩端）是否為回文。
* 遞迴定義：
* 基底 1：lo >= hi（空區間或單一字元）-> 是回文
* 基底 2：兩端字元不同 -> 不是回文
* 遞迴：兩端相同 -> 答案取決於「去掉頭尾後的內層區間」
*
* is_palindrome("level", 0, 4)
* 'l'=='l' -> is_palindrome("level", 1, 3)
* 'e'=='e' -> is_palindrome("level", 2, 2) <- lo==hi 觸底：1
*/
int is_palindrome(const char *s, int lo, int hi)
{
if (lo >= hi) /* 基底：區間縮到 0 或 1 個字元 */
return 1;
if (s[lo] != s[hi]) /* 基底：兩端不同，立即失敗 */
return 0;
return is_palindrome(s, lo + 1, hi - 1); /* 向中心縮小 */
}
/* 包一層方便呼叫：自動算範圍 */
int is_palindrome_str(const char *s)
{
return is_palindrome(s, 0, (int)strlen(s) - 1);
}
static void test(const char *s)
{
printf("\"%s\" -> %s\n", s, is_palindrome_str(s) ? "是回文" : "不是回文");
}
int main(void)
{
test("level"); /* 奇數長度回文 */
test("noon"); /* 偶數長度回文 */
test("hello"); /* 非回文 */
test("a"); /* 單一字元：回文 */
test(""); /* 空字串：視為回文 */
test("ab"); /* 兩字元非回文 */
test("abca"); /* 首尾同但內層不同 */
return 0;
}程式碼講解
- 兩個基底的順序：先檢查
lo >= hi再比字元。反過來的話， 空字串會先做s[0] != s[-1]——s[-1]是越界讀。 "abca"是關鍵測資：首尾都是'a'（第一層通過）， 內層"bc"不是回文——驗證「遞迴真的往下檢查了」， 只比首尾的偷懶實作會在這裡露餡。- 每層
lo+1、hi-1，區間長度每次縮 2 → 深度約 n/2，終止有保證。 - 基底條件
lo >= hi用>=而非==：偶數長度收斂時 lo 會跨過 hi （2,3 → 3,2），只寫==會擦身而過、繼續遞迴到越界—— 正是講義「基底要保證到得了」的實例。
範例輸出
"level" -> 是回文
"noon" -> 是回文
"hello" -> 不是回文
"a" -> 是回文
"" -> 是回文
"ab" -> 不是回文
"abca" -> 不是回文練習 5：print_binary —— 遞迴印二進位（難度：進階）
題目
寫遞迴函式 void print_binary(unsigned n)：印出 n 的二進位表示
（提示：先遞迴 n/2 再印 n%2）。
測試：0、1、小數字、2 的冪、8 位全 1（255）、unsigned 最大值。
解題思路
- 這就是 printd 的二進位版。十進位的「取尾巴/去尾巴」是
%10、/10； 二進位換成%2、/2。 - 為什麼「先遞迴、後輸出」順序就對？
數字的最低位最容易取得（
n%2），但印出時它要最後出現。 把「印自己」放在遞迴呼叫之後，等於利用呼叫堆疊把順序反過來：
print_binary(6)
print_binary(3) <- 先把「前面的位數」全部印完
print_binary(1) -> 印 '1'
印 3%2 -> '1'
印 6%2 -> '0'
輸出：110 ✓- 基底：
n < 2時直接印那一位。這讓print_binary(0)印出0（很多實作忘了 0 會印出空白）。 - 為什麼參數用
unsigned？ 位元表示對負數的「除以 2」語意混亂 （有號右移/除法向零取整的糾纏）；unsigned 讓/2就是「右移一位」，乾淨。
參考解答
/*
* ex5_print_binary.c
* ------------------
* 練習 5：print_binary —— 遞迴印出二進位（難度：進階）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_print_binary.c
* 執行：/tmp/out
*/
#include <stdio.h>
/*
* printd 的翻版（K&R §4.10）：
* 基底：n < 2 -> 直接印那一位（0 或 1）
* 遞迴：先印 n/2 的二進位（高位），回來再印 n%2（最低位）
*
* print_binary(6)：
* print_binary(3)：
* print_binary(1)：印 '1' <- 觸底
* 印 3%2 = '1'
* 印 6%2 = '0' -> 輸出 110
* 「先遞迴、後輸出」讓高位自然先印——不需要反轉緩衝區。
*/
void print_binary(unsigned n)
{
if (n >= 2)
print_binary(n / 2); /* 先處理高位 */
putchar((int)('0' + n % 2)); /* 再印自己這一位 */
}
int main(void)
{
unsigned tests[] = { 0, 1, 2, 5, 6, 10, 255, 1024, 4294967295u };
int n = (int)(sizeof tests / sizeof tests[0]);
for (int i = 0; i < n; i++) {
printf("%10u = ", tests[i]);
print_binary(tests[i]);
printf("\n");
}
return 0;
}程式碼講解
- 函式本體只有兩行，卻正確處理了所有輸入——遞迴版本的「印任意進位」 只要換掉那個 2 就能做八進位、十六進位（16 進位還需查表印 A-F）。
putchar('0' + n % 2)：n % 2是 0 或 1，加'0'變成字元。- 測資設計：
1024（2 的冪：1 後面十個 0）、255（8 個 1）、4294967295u（32 個 1，unsigned 上限）——各驗證一種位型態。 - 深度 = 位數 ≈ log₂(n)，32 位元最多 32 層——遞迴深度對數成長，毫無壓力 （對照練習 2 的線性深度，這種「每次砍半」的遞迴天生安全）。
- 想改成「固定寬度含前導零」（如印滿 8 位），改用參數帶「還剩幾位」 或迭代 + 位移遮罩更直接。
範例輸出
0 = 0
1 = 1
2 = 10
5 = 101
6 = 110
10 = 1010
255 = 11111111
1024 = 10000000000
4294967295 = 11111111111111111111111111111111練習 6：ackermann —— 呼叫次數的爆炸（難度：挑戰）
題目
實作 long ackermann(int m, int n) 並加上呼叫計數器，
實測 m ≤ 3、n ≤ 8 範圍內呼叫次數的成長，觀察「m 每加 1、成長等級整個升級」的現象。
Ackermann 函式的定義：
A(0, n) = n + 1
A(m, 0) = A(m-1, 1)
A(m, n) = A(m-1, A(m, n-1))解題思路
- 直接翻譯定義：三條規則就是三個分支，順序照抄——
m == 0是唯一的基底；另外兩條都是遞迴， 其中第三條是巢狀遞迴（遞迴呼叫的引數又是一個遞迴呼叫）， 這正是 Ackermann 兇猛的來源。 - 為什麼它會終止？ 每次呼叫要嘛
m變小、要嘛m不變但n變小 ——以 (m, n) 的字典序嚴格遞減，而字典序沒有無窮遞降鏈 → 必終止。 （這是比「單一參數變小」更精妙的終止論證，值得體會。） - 呼叫計數器：用一個檔案層級的
static long call_count， 進函式就++。注意這與「遞迴中誤用 static 存狀態」不同—— 計數器是觀測工具（只增不讀、不參與運算），不影響遞迴正確性。 每次量測前歸零。 - 對成長的感覺：
-
A(0,n) = n+1（一步到位）； -A(1,n) = n+2、A(2,n) = 2n+3（線性）； -A(3,n) = 2^(n+3) − 3（指數）——呼叫次數同步暴衝； -A(4,n)是疊冪（tetration）——A(4,2)的值有 19729 位數， 根本不可能算完。這就是「理論上可計算、實際上不可行」的教科書案例。 - 工程限制：m ≤ 3、n ≤ 8 是精心選的安全範圍
（
A(3,8)約 279 萬次呼叫，毫秒級；A(4,1)就要 28 億次呼叫）。
參考解答
/*
* ex6_ackermann.c
* ---------------
* 練習 6：ackermann —— 見識呼叫次數的爆炸（難度：挑戰）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex6_ackermann.c
* 執行：/tmp/out
*/
#include <stdio.h>
/* 全域呼叫計數器：每次進入函式就 +1 */
static long call_count;
/*
* Ackermann 函式（數學定義的直接翻譯）：
* A(0, n) = n + 1
* A(m, 0) = A(m-1, 1)
* A(m, n) = A(m-1, A(m, n-1)) <- 遞迴中還套遞迴！
* 它不是原始遞迴函式：成長速度超越任何固定層數的迴圈組合。
*/
long ackermann(int m, int n)
{
call_count++;
if (m == 0)
return n + 1;
if (n == 0)
return ackermann(m - 1, 1);
return ackermann(m - 1, (int)ackermann(m, n - 1));
}
int main(void)
{
printf("%-12s %-12s %-14s\n", "A(m, n)", "值", "呼叫次數");
printf("---------------------------------------\n");
/* m 固定看 n 的成長 */
for (int m = 0; m <= 3; m++) {
for (int n = 0; n <= 8; n++) {
if (m == 3 && n > 8)
break;
call_count = 0;
long v = ackermann(m, n);
printf("A(%d, %d) = %-12ld（%ld 次呼叫）\n",
m, n, v, call_count);
}
printf("---------------------------------------\n");
}
printf("觀察：m=3 時呼叫次數隨 n 呈指數暴衝；\n"
"A(4, 1) 就需要約 28 億次呼叫，A(4, 2) 的值有 19729 位數——\n"
"這就是「理論上可計算、實際上算不動」的經典示範。\n");
return 0;
}程式碼講解
ackermann(m - 1, (int)ackermann(m, n - 1))：內層遞迴的結果當外層的引數—— 求值順序是「先算內層、再呼叫外層」，巢狀遞迴的展開樹因此瘋狂分岔。- 數據會說話：m=2 時呼叫次數大致是二次成長（5, 14, 27, 44, …）， m=3 直接跳到指數（15, 106, 541, 2432, …每項約 ×4）—— 同一支函式，參數差 1，複雜度等級完全不同。
call_count每輪歸零、量完就印：把「看不見的遞迴成本」變成可觀察的數字， 這個手法同樣適用於量測天真費氏（單元範例 01 就是這麼做的）。- Ackermann 在真實世界的殘影：反 Ackermann 函數 α(n) 出現在 並查集（union-find）的複雜度分析——成長慢到對任何實際輸入 ≤ 5。
- 易錯處：忘了
n == 0這條中間規則（直接掉進第三條會讓 n 變 -1 一路發散）； 或用 int 存回傳值——A(3,8) = 2045還好，但再大就該用 long。
範例輸出
A(m, n) 值 呼叫次數
---------------------------------------
A(0, 0) = 1 （1 次呼叫）
A(0, 1) = 2 （1 次呼叫）
A(0, 2) = 3 （1 次呼叫）
A(0, 3) = 4 （1 次呼叫）
A(0, 4) = 5 （1 次呼叫）
A(0, 5) = 6 （1 次呼叫）
A(0, 6) = 7 （1 次呼叫）
A(0, 7) = 8 （1 次呼叫）
A(0, 8) = 9 （1 次呼叫）
---------------------------------------
A(1, 0) = 2 （2 次呼叫）
A(1, 1) = 3 （4 次呼叫）
A(1, 2) = 4 （6 次呼叫）
A(1, 3) = 5 （8 次呼叫）
A(1, 4) = 6 （10 次呼叫）
A(1, 5) = 7 （12 次呼叫）
A(1, 6) = 8 （14 次呼叫）
A(1, 7) = 9 （16 次呼叫）
A(1, 8) = 10 （18 次呼叫）
---------------------------------------
A(2, 0) = 3 （5 次呼叫）
A(2, 1) = 5 （14 次呼叫）
A(2, 2) = 7 （27 次呼叫）
A(2, 3) = 9 （44 次呼叫）
A(2, 4) = 11 （65 次呼叫）
A(2, 5) = 13 （90 次呼叫）
A(2, 6) = 15 （119 次呼叫）
A(2, 7) = 17 （152 次呼叫）
A(2, 8) = 19 （189 次呼叫）
---------------------------------------
A(3, 0) = 5 （15 次呼叫）
A(3, 1) = 13 （106 次呼叫）
A(3, 2) = 29 （541 次呼叫）
A(3, 3) = 61 （2432 次呼叫）
A(3, 4) = 125 （10307 次呼叫）
A(3, 5) = 253 （42438 次呼叫）
A(3, 6) = 509 （172233 次呼叫）
A(3, 7) = 1021 （693964 次呼叫）
A(3, 8) = 2045 （2785999 次呼叫）
---------------------------------------
觀察：m=3 時呼叫次數隨 n 呈指數暴衝；
A(4, 1) 就需要約 28 億次呼叫，A(4, 2) 的值有 19729 位數——
這就是「理論上可計算、實際上算不動」的經典示範。常見錯誤解法對照
| 錯誤寫法 | 症狀 | 正確做法 |
|---|---|---|
| 忘記基底情況 | 無窮遞迴 → 堆疊溢位 segfault | 先寫基底再寫遞迴；用 <=/>= 保證到得了 |
| 遞迴呼叫時參數沒變小 | 同上（stuck） | 每層必須向基底靠近（n-1、n/2、指標前進） |
is_palindrome 基底用 lo == hi |
偶數長度時 lo/hi 擦身而過，越界 | lo >= hi |
itoa 用 int 域的 n = -n 處理負數 |
INT_MIN 溢位（未定義行為） |
先放進 long 再取負 |
| 遞迴中用 static 變數存「寫到哪」 | 不可重入、收合時互相干擾 | 索引當參數傳遞、當回傳值送回 |
| 用天真遞迴算重複子問題（fib 式） | 呼叫次數指數爆炸 | 記憶化或改自底向上迭代 |