C語言遞迴函數詳解：以階乘計算為例掌握遞迴精髓

前言：何謂遞迴？

遞迴是函數在其函數體內直接或間接呼叫自身的技術。Turbo C 2.0 完整支援遞迴調用。遞迴能將複雜問題分解為同構的子問題，代碼極為精簡，但以堆疊記憶體為代價——每次調用佔用一層堆疊幀。

經典案例：階乘 n! 計算

數學定義

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

C 語言實現

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

unsigned long factorial(int n);  // 函數原型宣告

int main(void) {
    int m;
    puts("Calculate n!  n=?");
    scanf("%d", &m);
    printf("%d! = %lu\n", m, factorial(m));
    getch();
    return 0;
}

unsigned long factorial(int n) {
    if (n > 1)
        return n * factorial(n - 1);  // 遞迴呼叫
    else
        return 1UL;                    // 基礎情況
}

執行追蹤：factorial(5)

factorial(5)
  = 5 * factorial(4)
  = 5 * (4 * factorial(3))
  = 5 * 4 * (3 * factorial(2))
  = 5 * 4 * 3 * (2 * factorial(1))
  = 5 * 4 * 3 * 2 * 1
  = 120

每層調用在堆疊保存 n 與返回位址，基礎情況返回後逐層展開相乘。

遞迴的三要素

優缺點權衡

優點

• 代碼簡潔，直觀對應數學定義
• 天然適合樹、圖、分治類問題（漢諾塔、快速排序、樹遍歷）

缺點

• 堆疊溢位風險：深度遞迴耗盡堆疊空間（Turbo C 小型記憶體模型極明顯）
• 效率較低：函數調用開銷、重複計算（如費波那契數列朴素遞迴）
• 除錯困難：調用堆疊深、變數生命週期重疊

優化策略

1. 尾端遞迴優化：將遞迴呼叫置於函數末尾，編譯器可轉換為迴圈（Turbo C 2.0 不支援，需手動改寫）。
2. 記憶化：緩存子問題結果，避免重複計算。
3. 轉換為迭代：階乘、費波那契等線性遞迴均可用迴圈實現，效率更高、記憶體 O(1)。

何時選用遞迴？

• 問題天然具備遞迴結構（樹/圖遍歷、分治演算法）
• 遞迴深度可控（< 1000 層）
• 代碼可讀性優於效率需求

結語

遞迴是把雙面刃：善用能寫出極具數學美感的代碼，濫用則導致堆疊崩潰與效率災難。理解「基礎情況、遞迴步驟、縮小保證」三要素，並在實作前評估堆疊深度，是駕馭遞迴的關鍵。