C語言入門教程：遞歸函數詳解與經典案例

什麼是遞歸

遞歸是函數直接或間接調用自身的編程技巧。核心要素：

1. 基線條件：終止遞歸的條件，防止無限調用導致棧溢出。
2. 遞歸步驟：將問題分解為更小的同類子問題。

案例 1：最簡遞歸（無基線，會無限運行）

void prn(void) {
    printf("C++Builder 2009\n");
    prn(); // 無終止條件，需 Ctrl+C 強制結束
}

案例 2：帶基線條件的遞歸輸出

void prn(int num) {
    printf("%d\n", num);
    if (num > 0) prn(--num); // 基線：num <= 0 時停止
}
// prn(9) 輸出 9 8 7 ... 0

案例 3：字符串反轉

void revers(char *cs) {
    if (*cs) {
        revers(cs + 1); // 先遞歸到末尾
        putchar(*cs);   // 回溯時輸出，實現反序
    }
}
// revers("123456789") 輸出 987654321

案例 4：階乘計算

int factorial(int num) {
    if (num == 1) return 1;       // 基線
    return num * factorial(num - 1); // 遞歸步驟
}
// factorial(5) = 5*4*3*2*1 = 120

案例 5：整數轉二進制輸出

void IntToBinary(unsigned num) {
    int bit = num % 2;
    if (num > 1) IntToBinary(num / 2);
    putchar(bit ? '1' : '0'); // 回溯時輸出高位在前
}
// IntToBinary(255) 輸出 11111111

深度剖析：遞歸調用棧演示

void prn(unsigned n) {
    printf("%d: %p\n", n, &n); // A: 進入記錄
    if (n < 4) prn(n + 1);     // B: 遞歸調用
    printf("%d: %p\n", n, &n); // C: 返回記錄
}
// prn(1) 輸出分析見下圖

執行流程解析

1. 調用 prn(1)，執行 A 輸出第 1 行。
2. n=1 滿足條件，調用 prn(2)（B），輸出第 2 行……以此類推至 n=4。
3. n=4 時 A 執行（第 5 行），條件失效，執行 C（第 5 行）。
4. 函數返回給 n=3 的調用點，繼續執行 C（第 6 行）。
5. 依次返回 n=2（第 7 行）、n=1（第 8 行），遞歸結束。

每次遞歸都在棧上分配新的棧幀（含參數、局部變量、返回地址），&n 地址各不相同，直觀展示棧增長方向。

遞歸 vs 迭代

最佳實踐建議

• 永遠先寫基線條件，再寫遞歸步驟。
• 注意棧溢出風險：深度超過數萬層可能耗盡棧（典型 1-8MB）。
• 尾遞歸可手動改寫為迭代，或依賴編譯器優化（-O2/-O3）。
• 調試時打印進入/退出日誌，觀察調用棧變化。