遞歸還是迭代？Fibonacci 數列的三種算法演進與矩陣快速冪優化

引子：教科書級遞歸的性能陷阱

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

計算 f(5) 需 12 次加法，大量重複子問題（f(3) 算兩次），時間複雜度 O(2^n)，棧深度 O(n)，大 n 直接棧溢出。

第一優化：迭代累加（動態規劃底層邏輯）

unsigned long fibonacci(int n) {
    if (n <= 2) return 1;
    unsigned long f0 = 1, f1 = 1, temp;
    for (int i = 3; i <= n; ++i) {
        temp = f0 + f1;
        f0 = f1;
        f1 = temp;
    }
    return f1;
}

• 時間 O(n)，空間 O(1)。
• f(5) 僅 3 次加法，消除重複計算。

第二優化：矩陣快速冪 —— O(log n)

利用矩陣關係：

[f(n) ] = [1 1]^(n-2) * [f(2)]

[f(n-1)] [1 0] [f(1)]

即計算矩陣 M = [[1,1],[1,0]] 的 (n-2) 次方，結果首行兩元素之和為 f(n)。

遞歸版快速冪（分治）

void matrix_power(ull a,ull b,ull c,ull d, int n,
                  ull *aa,ull *bb,ull *cc,ull *dd) {
    if (n == 1) { *aa=a; *bb=b; *cc=c; *dd=d; return; }
    ull xa,xb,xc,xd;
    if (n & 1) { // 奇數：M * M^(n-1)
        matrix_power(a,b,c,d, n-1, &xa,&xb,&xc,&xd);
        *aa = a*xa + b*xc; *bb = a*xb + b*xd;
        *cc = c*xa + d*xc; *dd = c*xb + d*xd;
    } else { // 偶數：(M^(n/2))^2
        matrix_power(a,b,c,d, n>>1, &xa,&xb,&xc,&xd);
        *aa = xa*xa + xb*xc; *bb = xa*xb + xb*xd;
        *cc = xc*xa + xd*xc; *dd = xc*xb + xd*xd;
    }
}

時間 O(log n)，但仍用遞歸，棧深 O(log n)。

終極優化：非遞歸快速冪（二進制分解法）

核心洞察：n 的二進制位為 1 的位置對應 2 的冪次。
M^n = Π M^(2^k)（對所有二進制位 k 為 1 的項相乘）。

迭代過程：

1. 初始 result = I（單位矩陣），base = M。
2. 掃描 n 的二進制位（從低到高）：
   • 若當前位為 1：result = result * base。
   • base = base * base（平方）。
   • n >>= 1。
3. 返回 result。

完整非遞歸實現

using ull = unsigned long long;

void multiply(ull *aa, ull *bb, ull *cc, ull *dd,
              ull a, ull b, ull c, ull d) {
    ull ta = *aa, tb = *bb, tc = *cc, td = *dd;
    *aa = ta*a + tb*c; *bb = ta*b + tb*d;
    *cc = tc*a + td*c; *dd = tc*b + td*d;
}

void matrix_power(ull a, ull b, ull c, ull d, int n,
                  ull *aa, ull *bb, ull *cc, ull *dd) {
    ull xa = a, xb = b, xc = c, xd = d; // base matrix
    *aa = 1; *bb = 0; *cc = 0; *dd = 1; // result = I
    bool first = true;

    while (n > 0) {
        if (n & 1) {
            if (first) { // 第一次直接賦值避免乘 I
                *aa = a; *bb = b; *cc = c; *dd = d;
                first = false;
            } else {
                multiply(aa, bb, cc, dd, xa, xb, xc, xd);
            }
        }
        // base = base * base
        ull ta = xa*xa + xb*xc;
        ull tb = xa*xb + xb*xd;
        ull tc = xc*xa + xd*xc;
        ull td = xc*xb + xd*xd;
        xa = ta; xb = tb; xc = tc; xd = td;
        n >>= 1;
    }
}

性能對比（n=90）

遞歸的哲學思考

• 遞歸是「人的思維簡化」，將問題分解為相似子問題，代碼短但隱藏棧開銷。
• 編譯器尾調用優化（TCO）僅適用於尾遞歸，Fibonacci 雙遞歸無法優化。
• 工程中：能用迭代/狀態機解決的，盡量不用遞歸；必須遞歸時（樹遍歷、分治），評估最大深度並設置棧大小或改寫非遞歸版。

本文出自 “菜鳥浮出水” 博客，原文地址：https://rangercyh.blog.51cto.com/1444712/292806