Java 遞歸與迭代實現斐波那契數列：兔子繁殖問題

問題背景

斐波那契數列源於兔子繁殖模型：第 1、2 月各 1 對，從第 3 月起每對成年兔每月產 1 對新兔。數列：1, 1, 2, 3, 5, 8, 13, 21...

遞歸實現（教學用，效率低）

public static int fibRec(int n) {
    if (n == 1 || n == 2) return 1;
    return fibRec(n-1) + fibRec(n-2); // 指數級重複計算
}

迭代實現（生產推薦，O(n) 時間，O(1) 空間）

public static long fibIter(int n) {
    if (n <= 2) return 1;
    long a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

動態規劃 / 記憶化遞歸

private static long[] memo = new long[100];
public static long fibMemo(int n) {
    if (n <= 2) return 1;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fibMemo(n-1) + fibMemo(n-2);
}

矩陣快速冪 (O(log n))

// [F(n+1) F(n)  ]   [1 1]^n
// [F(n)   F(n-1)] = [1 0]
// 利用矩陣快速冪求第 n 項，適合超大 n

測試輸出前 20 項

for (int i = 1; i <= 20; i++) {
    System.out.println("F(" + i + ") = " + fibIter(i));
}

總結