C語言基礎教程（五）：遞迴函數詳解與階乘實作

遞迴：函數自我呼叫的藝術

Turbo C 2.0 允許函數直接或間接呼叫自己，這項機制稱為遞迴。遞迴能將複雜問題分解為同樣結構的子問題，使程式碼極度精簡、邏輯清晰；代價是每層呼叫需消耗堆疊空間，深度過大易導致堆疊溢位。理解「基底條件」與「遞迴步驟」是掌握遞迴的關鍵。

經典範例：計算 n! (階乘)

階乘的數學定義天然具備遞迴特性：

• 基底條件：0! = 1! = 1
• 遞迴步驟：n! = n × (n-1)! (n > 1)

#include <stdio.h>
#include <conio.h>

unsigned long mul(int n);   /* 函數原型：回傳 unsigned long 防溢位 */

int main(void)
{
    int m;
    puts("Calculate n!  n=?");
    scanf("%d", &m);
    printf("%d! = %lu\n", m, mul(m));  /* %lu 對應 unsigned long */
    getch();
    return 0;
}

/* 遞迴函數：計算 n! */
unsigned long mul(int n)
{
    unsigned long p;
    if (n > 1)
        p = n * mul(n - 1);   /* 遞迴呼叫 */
    else
        p = 1UL;              /* 基底條件 */
    return p;
}

執行流程追蹤 (以 n=5 為例)

1. mul(5) → 5 * mul(4)
2. mul(4) → 4 * mul(3)
3. mul(3) → 3 * mul(2)
4. mul(2) → 2 * mul(1)
5. mul(1) 觸發基底條件，回傳 1
6. 層層回傳：2→6→24→120

關鍵技術細節

遞迴 vs 迴圈：效能與適用場景

• 迴圈版本：僅需一個區域變數，O(1) 空間，速度最快，適合生產環境。
• 遞迴版本：O(n) 堆疊空間，函數呼叫開銷大，但邏輯與數學定義完美對應，適合教學、樹狀結構遍歷、分治演算法（如快速排序、合併排序）。

進階話題：尾端遞迴優化

若將乘法移至參數傳遞：

unsigned long mul_tail(int n, unsigned long acc)
{
    return (n <= 1) ? acc : mul_tail(n - 1, n * acc);
}

編譯器若支援尾端呼叫優化 (TCO)，可將其轉為迴圈，消除堆疊增長。ANSI C 不強制要求 TCO，現代編譯器 (GCC/Clang/MSVC 在優化等級開啟時) 多支援此優化。

常見錯誤與除錯技巧

1. 遺漏基底條件 → 無限遞迴 → Stack Overflow。
2. 基底條件判斷錯誤 → 計算結果偏差 (如 0! 算成 0)。
3. 資料型別過小 → 整數溢位產生負數或錯誤值。
4. 除錯建議：在函數入口加入 printf("mul(%d)\\n", n); 觀察呼叫深度。

遞迴是程式設計的利器，掌握其「分解-解決-合併」的思維模式，對演算法設計與資料結構操作大有裨益。實務上請依據問題規模、效能需求與程式碼可讀性，在遞迴與迴圈間做權衡選擇。