遞歸 vs 循環：斐波那契數列性能實測與系統開銷對比

遞歸代碼優雅簡潔，但對於斐波那契數列這類重疊子問題，遞歸會導致指數級調用爆炸，嚴重拖垮性能甚至癱瘓系統。本文通過實測對比遞歸與迭代實現，直觀展示效率差距，並給出工程選型建議。

實測場景：計算 F(40)

// 遞歸實現
public static long fibRecursive(int n) {
    if (n <= 2) return 1;
    return fibRecursive(n-1) + fibRecursive(n-2);
}

// 迭代實現
public static long fibIterative(int n) {
    if (n <= 2) return 1;
    long a = 1, b = 1, c = 0;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

實測結果（Eclipse 環境）

原理深度解析

遞歸的指數級爆炸

遞歸樹中大量重複子問題：F(n) 調用 F(n-1) 和 F(n-2)，而 F(n-1) 又調用 F(n-2) 和 F(n-3)... 總調用次數約 O(1.618^n)（黃金比例指數）。

迭代的線性優勢

自底向上，僅保留前兩項，時間 O(n)，空間 O(1)，無重複計算，無棧溢出風險。

優化遞歸的可能路徑（了解即可）

• 記憶化搜索：緩存中間結果，時間降為 O(n)，但仍需 O(n) 棧空間。
• 尾遞歸優化：Java 編譯器不支持 TCO，手寫尾遞歸仍會棧溢出。
• 矩陣快速冪/通項公式：O(log n)，屬於算法進階範疇。

工程選型鐵律

1. 優先迭代：凡是可用循環解決的問題，堅決不用遞歸。
2. 遞歸適用場景：樹/圖遍歷、分治算法（歸並排序）、深度未知且數據量可控的結構處理。
3. 必須遞歸時：評估最大深度，設置 -Xss 增大棧，或改寫為顯式棧模擬遞歸。
4. 性能敏感路徑：嚴禁遞歸，除非經過嚴格基準測試驗證。

遞歸是思維工具，迭代是工程工具。能不用遞歸，就不用遞歸——這不是保守，是對系統穩定性的敬畏。

下次面試遇到「斐波那契怎麼實現」，請自信寫出迭代版，並補充：「遞歸版僅供教學演示，生產環境堅決不用」。