經典遞歸題：斐波那契兔子問題的 Java 實現與優化演進

問題還原：一對兔子的繁衍邏輯

古典問題：3個月起每個月都生一對兔子，小兔子長到第三個月後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？

規律推導：從兔子年齡結構到數列模型

將兔子按年齡分為三組：

• 小兔：出生第 1 個月
• 中兔：第 2 個月
• 大兔：第 3 個月及以上 (具備繁殖能力)

核心規律：第 n 月總數 = 第 n-1 月總數 + 第 n-2 月總數 (n ≥ 3)。這正是斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21...

Java 實現：從遞歸到動態規劃

版本 1：朴素遞歸 (教學用，生產環境禁用)

public class RabbitRecursive {
    public static long fibonacci(int month) {
        if (month <= 2) return 1;
        return fibonacci(month - 1) + fibonacci(month - 2);
    }
    
    public static void main(String[] args) {
        for (int i = 1; i <= 20; i++) {
            System.out.printf("第 %2d 月: %,d 對%n", i, fibonacci(i));
        }
    }
}
// 缺點：指數級時間複雜度 O(2^n)，month=50 時需數小時

版本 2：記憶化遞歸 (自頂向下 DP)

public class RabbitMemoization {
    private static Map memo = new HashMap<>();
    
    static { memo.put(1, 1L); memo.put(2, 1L); }
    
    public static long fibonacci(int month) {
        if (memo.containsKey(month)) return memo.get(month);
        long result = fibonacci(month - 1) + fibonacci(month - 2);
        memo.put(month, result);
        return result;
    }
    // 時間 O(n)，空間 O(n)，解決重複計算

版本 3：迭代動態規劃 (自底向上，最優空間)

public class RabbitDP {
    public static long fibonacci(int month) {
        if (month <= 2) return 1;
        long prev2 = 1, prev1 = 1, current = 0;
        for (int i = 3; i <= month; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
    // 時間 O(n)，空間 O(1)，生產環境首選

版本 4：矩陣快速冪 (對數級時間，超大月份)

public class RabbitMatrix {
    // [[1,1],[1,0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
    private static 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]}
        };
    }
    
    private static long[][] power(long[][] base, int n) {
        long[][] result = {{1,0},{0,1}}; // 單位矩陣
        while (n > 0) {
            if ((n & 1) == 1) result = multiply(result, base);
            base = multiply(base, base);
            n >>= 1;
        }
        return result;
    }
    
    public static long fibonacci(int month) {
        if (month <= 2) return 1;
        long[][] base = {{1,1},{1,0}};
        long[][] res = power(base, month - 2);
        return res[0][0] + res[0][1]; // F(n) = F(n-1) + F(n-2)
    }
    // 時間 O(log n)，適合 month > 10^6 等極大場景

大數處理：突破 long 極限

斐波那契數列增長極快，long (第 92 個月溢出) 很快不夠用。使用 BigInteger：

public class RabbitBigInteger {
    public static BigInteger fibonacci(int month) {
        if (month <= 2) return BigInteger.ONE;
        BigInteger prev2 = BigInteger.ONE, prev1 = BigInteger.ONE, current;
        for (int i = 3; i <= month; i++) {
            current = prev1.add(prev2);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
    
    public static void main(String[] args) {
        System.out.println("第 100 月: " + fibonacci(100)); 
        // 354224848179261915075
        System.out.println("第 500 月位數: " + fibonacci(500).toString().length()); 
        // 105 位
    }
}

性能對比總結

擴展思考

• 通項公式 (Binet 公式)：F(n) = (φ^n - ψ^n)/√5，φ=(1+√5)/2。涉及浮點精度，大 n 不推薦直接用
• Pisano 周期：求 F(n) mod m 時，利用模運算周期性可大幅優化
• 泛化兔子問題：成熟週期 k 個月、每產 m 對、壽命 L 月 → 線性遞歸關係，同樣可用矩陣快速冪

總結

兔子問題是遞歸與動態規劃的絕佳入門教材。從指數級遞歸到常數空間迭代，再到對數級矩陣快速冪，每一步優化都對應著演算法設計的核心思想：消除重複子問題、空間換時間、數學結構加速。實際開發中，迭代 DP + BigInteger 已能覆蓋 99% 的業務場景，既簡潔又可靠。