您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言遞迴函數效能分析：階乘與費波那契的遞迴 vs 迭代對決

編輯：關於C

前言

遞迴是程式設計中極具表達力的技巧，但「能用遞迴不代表該用遞迴」。本文以階乘與費波那契數列為例，實測遞迴與迭代的效能差異，並分析遞迴的隱性成本。

案例一：階乘

遞迴版本

long factorial_recursive(int n) {
    if (n <= 0) return 1;
    return n * factorial_recursive(n - 1);
}

迭代版本

long factorial_iterative(int n) {
    long result = 1;
    while (n > 1) {
        result *= n;
        n--;
    }
    return result;
}

效能差異分析

呼叫開銷：遞迴每層需建立堆疊幀（儲存返回位址、區域變數、暫存器），迭代僅有一次函式呼叫。
堆疊深度：遞迴深度 = n，大 n 易導致堆疊溢位；迭代無此風險。
編譯器優化：現代編譯器（-O2/-O3）可將尾端遞迴優化為迭代，但非尾端遞迴（如費波那契）無法優化。

案例二：費波那契數列

遞迴版本（指數級複雜度）

long fibonacci_recursive(int n) {
    if (n <= 2) return 1;
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
}

呼叫樹呈二元樹，節點數 ≈ 2^n，大量重複計算（如 fib(3) 被計算多次）。

迭代版本（線性複雜度）

long fibonacci_iterative(int n) {
    if (n <= 2) return 1;
    long first = 1, second = 1, result = 0;
    while (n > 2) {
        n--;
        second = first;
        first = result;
        result = first + second;
    }
    return result;
}

僅需 O(n) 時間、O(1) 空間，保留前兩項即可推導下一項。

動態規劃/備忘錄優化遞迴

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

加上備忘錄後遞迴也能達 O(n)，但仍有函式呼叫開銷與堆疊風險。

實測數據參考（n=40）

實作方式	時間複雜度	空間複雜度	相對執行時間
遞迴費波那契	O(2^n)	O(n) 堆疊	極慢（秒級）
遞迴+備忘錄	O(n)	O(n) 堆疊+陣列	快（毫秒級）
迭代費波那契	O(n)	O(1)	最快（微秒級）
遞迴階乘	O(n)	O(n) 堆疊	中等
迭代階乘	O(n)	O(1)	最快

遞迴適用場景 vs 慎用場景

✅ 適合遞迴	❌ 慎用遞迴
樹/圖遍歷（DFS）、分治演算法（快排、合併排序）	線性遞推可用迭代替代（階乘、費波那契、陣列求和）
問題自然具備遞迴結構（漢諾塔、括號匹配）	深度不可控或可能極大（鏈表反轉、深層巢狀結構）
尾端遞迴且編譯器支援優化	嵌入式/即時系統：堆疊大小受限