費波那契數列：遞歸與迭代兩種實現方式效能對比

費波那契數列（Fibonacci）是演算法入門經典案例。本文對比遞歸與迭代兩種實現，直觀展示效能差距，幫助理解為何生產環境應優先選擇迭代或動態規劃。

遞歸實現（指數級複雜度）

public static long recursive(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return recursive(n - 1) + recursive(n - 2);
}

缺點：大量重複子問題計算，時間複雜度 O(2^n)，n=40 時明顯卡頓，n=50 近乎不可用。

迭代實現（線性複雜度）

public static long loop(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    long fib1 = 0, fib2 = 1, sum = 0;
    for (int i = 2; i <= n; i++) {
        sum = fib1 + fib2;
        fib1 = fib2;
        fib2 = sum;
    }
    return sum;
}

優點：單次遍歷，時間 O(n)、空間 O(1)，極高效穩定。

效能實測對比（n=40）

// 遞歸：約 500-1000 ms
// 迭代：< 1 ms

進階優化方向

• 記憶化遞歸：用 Map 或陣列緩存中間結果，將遞歸優化至 O(n)。
• 矩陣快速冪：O(log n) 解法，適合極大 n（如 n > 10^9）。
• 通項公式：貝祖公式直接計算，涉及浮點精度問題。

總結

教學理解用遞歸，工程落地用迭代。理解「重複子問題」與「狀態轉移」是動態規劃入門鑰匙。