Java 經典兔子問題：費波那契數列遞歸與迭代實現

「一對兔子，三個月性成熟，之後每月產一對，兔子永不死，求每月總對數」——這是著名的費波那契數列問題，也是遞歸、動態規劃、矩陣快速冪等算法的絕佳入門案例。本文從建模分析到多種 Java 實現，幫你徹底吃透這道經典題。

問題建模：從兔子到數學

• 第 1 月：1 對（幼兔）
• 第 2 月：1 對（亞成熟）
• 第 3 月：2 對（1 成熟 + 1 幼兔）
• 第 4 月：3 對
• 第 5 月：5 對
• ...

規律：F(n) = F(n-1) + F(n-2)（n ≥ 3），F(1)=1, F(2)=1。即費波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

五種 Java 實現：由淺入深

1. 遞歸（教學演示，生產禁用）

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

• 時間複雜度：O(2^n)，指數級爆炸，n=50 即卡死。
• 空間複雜度：O(n)（調用棧）。
• 痛點：大量重複計算（如 fib(5) 會重複算 fib(3)、fib(2)）。

2. 遞歸 + 備忘錄（自頂向下動態規劃）

Map<Integer, Long> memo = new HashMap<>();
public long fibMemo(int n) {
    if (n <= 2) return 1;
    if (memo.containsKey(n)) return memo.get(n);
    long res = fibMemo(n-1) + fibMemo(n-2);
    memo.put(n, res);
    return res;
}

• 時間/空間：O(n)，消除重複計算。
• 適用於需要遞歸思維的場景（如樹形 DP）。

3. 迭代（自底向上動態規劃，推薦生產）

public long fibIterative(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;
}

• 時間 O(n)，空間 O(1)，無棧溢出風險，性能最優。

4. 矩陣快速冪（O(log n)，大數場景）

| F(n)   |   | 1 1 |^(n-2)   | F(2) |
| F(n-1) | = | 1 0 |         | F(1) |

public long fibMatrix(long n) {
    if (n <= 2) return 1;
    long[][] base = {{1,1},{1,0}};
    long[][] res = matrixPow(base, n-2);
    return res[0][0] + res[0][1]; // F(2)+F(1)
}
private long[][] matrixPow(long[][] m, long p) {
    long[][] result = {{1,0},{0,1}}; // 單位矩陣
    while (p > 0) {
        if ((p & 1) == 1) result = multiply(result, m);
        m = multiply(m, m);
        p >>= 1;
    }
    return result;
}
private long[][] multiply(long[][] a, long[][] b) {
    return new long[][]{
        {a[0][0]*b[0][0]+a[0][1]*b[1][0], a[0][0]*b[0][1]+a[0][1]*b[1][1]},
        {a[1][0]*b[0][0]+a[1][1]*b[1][0], a[1][0]*b[0][1]+a[1][1]*b[1][1]}
    };
}

• 時間 O(log n)，適合極大 n（如 n=10^9）。
• 需配合 BigInteger 防溢出。

5. 通項公式（Binet 公式，浮點近似）

F(n) = (φ^n - ψ^n) / √5,  φ=(1+√5)/2, ψ=(1-√5)/2

• O(1) 但浮點誤差大，n>70 不精確，僅供數學鑒賞。

實戰擴展：兔子問題變體

總結與最佳實踐

1. 面試/教學：會寫遞歸、迭代、備忘錄三種，能分析時空複雜度。
2. 生產環境：首選 迭代 O(1) 空間；n 極大（>10^6）用 矩陣快速冪 + BigInteger。
3. 避坑：long 最大存 F(92)，超出必用 BigInteger；遞歸深度超棧限制（默認 ~1萬層）。

兔子問題看似簡單，實則串聯了遞歸、動態規劃、線性代數、數論等核心知識。吃透它，動態規劃入門就打下堅實基礎了！

1. 上一篇文章： 《Thinking in Java》讀書筆記：第 1-3 章 核心概念深度解析
2. 下一篇文章： CSS3 動畫完整指南：@keyframes 規則與 animation 屬性詳解

Java 相關知識

Eclipse RCP 技術架構深度解析：從插件機制到豐富客戶端平台

什麼是 Eclipse RCP？ Rich Client P

Java 設計模式精講：Singleton 單例模式三種實作與最佳實踐

核心意圖 確保類別在 JVM 中僅有一個實例，並提供全域存取

Spring AOP 入門（九）：面向切面編程核心概念與術語詳解

什麼是 AOP？ AOP (Aspect Oriented

Eclipse RCP 客戶端多執行緒開發實戰指南

Eclipse Rich Client Platform (