經典遞迴題目：費波那契數列兔子繁殖問題 Java 實作

問題描述

一對兔子，從出生後第 3 個月起每個月生一對兔子，小兔子長到第 4 個月後也開始生殖。假設兔子不死，求第 n 個月兔子總對數。這是經典的費波那契數列（Fibonacci Sequence）問題：

F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n>2)

兩種 Java 實作風格

寫法一：靜態方法單一類別

public class Exp2 {
    public static void main(String[] args) {
        for (int i = 1; i <= 20; i++) {
            System.out.println("第 " + i + " 個月：" + f(i) + " 對");
        }
    }

    public static int f(int x) {
        if (x == 1 || x == 2) return 1;
        return f(x - 1) + f(x - 2);
    }
}

寫法二：分離數學類別（符合單一職責原則）

public class Exp2 {
    public static void main(String[] args) {
        MathUtil math = new MathUtil();
        for (int i = 1; i <= 20; i++) {
            System.out.println("第 " + i + " 個月：" + math.f(i) + " 對");
        }
    }
}

class MathUtil {
    public int f(int x) {
        if (x == 1 || x == 2) return 1;
        return f(x - 1) + f(x - 2);
    }
}

效能分析與優化方向

迭代版本範例（推薦生產使用）

public static 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;
}

遞迴深度限制提醒

Java 預設堆疊深度約 10,000 層左右，f(50) 即可能導致 StackOverflowError。實務上請改用迭代或 BigInteger 處理大數。