C語言遞歸函數效能陷阱：階乘與斐波那契的迭代優化

C語言遞歸函數效能陷阱：階乘與斐波那契的迭代優化

遞歸代碼簡潔優雅，但對於階乘、斐波那契等問題，遞歸往往是效能殺手。本文通過對比揭示遞歸的堆棧開銷問題，並給出高效的迭代替代方案。

遞歸的隱形成本

• 每次函數調用需分配棧幀（保存返回地址、局部變量、寄存器）
• 深度遞歸導致棧溢出風險
• 重複計算（如斐波那契）導致指數級時間複雜度

案例一：階乘計算

遞歸版（低效）

long factorial_recursive(int n) {
    if (n <= 0) return 1;
    return n * factorial_recursive(n - 1);  // n 次函數調用
}

迭代版（高效）

long factorial_iterative(int n) {
    long result = 1;
    while (n > 1) {
        result *= n;
        n--;
    }
    return result;  // 單循環，O(1) 空間
}

案例二：斐波那契數列

遞歸版（極度低效）

long fibonacci_recursive(int n) {
    if (n <= 2) return 1;
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);  // 指數級調用
}

計算 fib(40) 需約 3 億次調用，耗時秒級。

迭代版（線性時間）

long fibonacci_iterative(int n) {
    if (n <= 2) return 1;
    long a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;  // O(n) 時間，O(1) 空間
}

效能對比表 (n=40)

何時適合用遞歸？

• 問題天然遞歸結構（樹遍歷、圖 DFS、分治算法）
• 遞歸深度可控（如 log n 深度的二分查找、歸併排序）
• 代碼可讀性提升遠超效能損失的場景
• 支持尾調用優化的語言/編譯器（C 需開啟 -O2/-O3 且寫成尾遞歸）

尾遞歸優化示例

// 尾遞歸版階乘（編譯器優化後等價於迭代）
long factorial_tail(int n, long acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // 遞歸調用是最後操作
}
// 調用：factorial_tail(5, 1)