C 語言遞迴函數教學：從階乘到遞迴思維的建立

編輯：關於C語言

什麼是遞迴

函數在其本體內直接或間接呼叫自身，稱為遞迴呼叫。遞迴函數必須包含兩要素：

基礎情況：不再遞迴、直接返回結果的終止條件。
遞迴步驟：將問題縮小為相同性質的子問題，呼叫自身解決。

經典範例：階乘計算

數學定義

n! = 1                    (n = 0, 1)
n! = n × (n-1)!           (n > 1)

C 實現


long factorial(int n) {
    if (n < 0) {
        printf("輸入錯誤：負數無階乘\n");
        return -1;
    }
    if (n == 0 || n == 1) return 1;   // 基礎情況
    return n * factorial(n - 1);      // 遞迴步驟
}

執行追蹤：factorial(5)

factorial(5)
  5 * factorial(4)
    4 * factorial(3)
      3 * factorial(2)
        2 * factorial(1)
          1                     ← 基礎情況，開始回溯
        2 * 1 = 2
      3 * 2 = 6
    4 * 6 = 24
  5 * 24 = 120

每層遞迴在呼叫堆疊分配幀（參數、區域變數、返回位址）。
深度 = n，空間複雜度 O(n)。
若無基礎情況或條件錯誤 → 無限遞迴 → 堆疊溢位。

遞迴 vs 迭代

維度	遞迴	迭代
可讀性	數學定義直覺映射，代碼簡潔	需手動管理狀態變數
空間效能	O(深度) 堆疊空間	O(1) 常數空間
時間效能	函數呼叫開銷，可能重複計算	通常更快
適用場景	樹/圖遍歷、分治、回溯、動態規劃	線性累積、簡單迴圈

階乘迭代寫法（更優）


long factorial_iter(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

必須用遞迴的問題

樹結構操作：二元樹遍歷、深度計算、鏡像翻轉。
分治演算法：快速排序、合併排序、大整數乘法 (Karatsuba/FFT)。
回溯搜尋：八皇后、迷宮走法、子集生成、正則表達式匹配。
動態規劃備忘錄：遞迴 + 緩存 = 自頂向下 DP。

遞迴優化技巧

尾遞迴優化 (TCO)


// 尾遞迴：遞迴呼叫為最後一步操作
long fact_tail(int n, long acc) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, n * acc);  // 編譯器可優化為迴圈
}

GCC/Clang -O2、MSVC /O2 可將尾遞迴優化為跳轉，消除堆疊增長。
C 標準不保證 TCO，生產碼不應依賴。

備忘錄化


long fib_memo(int n) {
    static long memo[100] = {0};
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    return memo[n] = fib_memo(n-1) + fib_memo(n-2);
}