Java 非遞歸迭代法高效生成斐波那契數列

斐波那契數列是經典算法題，遞歸解法雖簡潔但效率極低（指數級時間複雜度）。本文展示基於迭代的 O(n) 時間、O(n) 空間實現，並說明 Integer 溢出邊界與應對策略。

迭代實現核心邏輯

僅需兩個變量滾動保存前兩項，循環累加生成後續項，存入列表返回。避免遞歸棧溢出與重複計算。

完整代碼

import java.util.ArrayList;
import java.util.List;

public class Fibonacci {

    /**
     * 生成前 size 項斐波那契數列
     * @param size 期望項數（>0）
     * @return 包含前 size 項的列表
     * @throws IllegalArgumentException size < 0
     */
    public static List<Integer> generate(int size) {
        if (size < 0) {
            throw new IllegalArgumentException("size 不能為負數");
        }
        List<Integer> result = new ArrayList<>(size);
        if (size == 0) return result;
        result.add(0);
        if (size == 1) return result;
        result.add(1);
        int first = 0, second = 1;
        for (int i = 2; i < size; i++) {
            int next = first + second; // 可能溢出，見下文
            first = second;
            second = next;
            result.add(next);
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> fib = generate(10);
        fib.forEach(n -> System.out.print(n + "\t")); // 0 1 1 2 3 5 8 13 21 34
    }
}

Integer 溢出邊界分析

• Integer.MAX_VALUE = 2,147,483,647（約 21.4 億）
• 斐波那契數列第 46 項 = 1,836,311,903（安全）
• 第 47 項 = 2,971,215,073 > MAX_VALUE → 溢出變負數

因此 size >= 47 時會發生溢出。原文提到 983 是錯誤的（可能混淆了長整型）。

解決溢出的三種方案

1. 改用 Long：支援到第 92 項（19 位數）。
2. 使用 BigInteger：任意大小，性能稍差但最安全。
3. 拋出異常或截斷：檢測溢出後停止生成。

BigInteger 版本示例（推薦生產環境）

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public static List<BigInteger> generateBig(int size) {
    if (size < 0) throw new IllegalArgumentException("size < 0");
    List<BigInteger> res = new ArrayList<>(size);
    if (size == 0) return res;
    res.add(BigInteger.ZERO);
    if (size == 1) return res;
    res.add(BigInteger.ONE);
    BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
    for (int i = 2; i < size; i++) {
        BigInteger c = a.add(b);
        a = b;
        b = c;
        res.add(c);
    }
    return res;
}

性能對比

其中 M 為大整數位數。對於常規業務（size < 50），Long 版本性能最佳且足夠安全。