斐波那契數列「一增一減」迭代算法原理深度解析

代碼復盤

int f = 0;
int g = 1;
for (int i = 0; i <= 15; i++) {
    println(f);
    f = f + g;
    g = f - g;
}

輸出：0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

問題一：為什麼「一增一減」能產生斐波那契數列？

設第 n 次循環開始時變量值為 f(n)、g(n)，執行體為：

f(n+1) = f(n) + g(n)
g(n+1) = f(n+1) - g(n)

將第一式代入第二式：

g(n+1) = (f(n) + g(n)) - g(n) = f(n)

即 g(n+1) = f(n)。下一輪循環：

f(n+2) = f(n+1) + g(n+1) = f(n+1) + f(n)

這正是斐波那契遞推公式：F(n+2) = F(n+1) + F(n)。

問題二：初值 f=0, g=1 如何確定？

斐波那契數列標準定義：F(0)=0, F(1)=1。對應代碼：

• 循環第 0 次打印 f=0 → F(0)
• 更新後 f=1, g=0
• 循環第 1 次打印 f=1 → F(1)
• 更新後 f=1, g=1
• 循環第 2 次打印 f=1 → F(2)

初值直接對應數列前兩項，無需額外判斷邊界。

數學本質：狀態機視角

該算法維護一個二維狀態向量 [f, g]^T，每次迭代應用線性變換矩陣：

[f(n+1)]   [1 1] [f(n)]
[g(n+1)] = [1 0] [g(n)]

特徵多項式 λ² - λ - 1 = 0，特徵根即黃金分割率 φ = (1+√5)/2，這也是斐波那契數列通項公式（比奈公式）的來源。

對比：遞歸與動態規劃

// 遞歸：指數級複雜度 O(2^n)，極其低效
int fibRec(int n) {
    if (n <= 1) return n;
    return fibRec(n-1) + fibRec(n-2);
}

// DP 數組：O(n) 時間，O(n) 空間
int fibDP(int n) {
    int[] dp = new int[n+1];
    dp[0]=0; dp[1]=1;
    for (int i=2; i<=n; i++) dp[i]=dp[i-1]+dp[i-2];
    return dp[n];
}

// 「一增一減」：O(n) 時間，O(1) 空間，最優

總結

「一增一減」巧妙利用變量交換實現狀態轉移，本質是斐波那契遞推關係的常數空間迭代實現。初值對應數列定義，邏輯自洽且極致高效，是教學與工程雙重優選。