遞歸算法優化實戰：從指數級爆炸到線性時間的 K 階斐波那契求解

遞歸算法優化實戰：從指數級爆炸到線性時間的 K 階斐波那契求解

遞歸代碼簡潔優雅，但直接遞歸往往因重複計算導致指數級時間複雜度。本文以「前 K 項為 1，後續項為前 K 項之和」的廣義斐波那契數列為例，對比朴素遞歸與動態規劃優化，展示從 O(k^n) 到 O(n*k) 的劇烈性能躍升。

一、問題定義與朴素遞歸實現

// 朴素遞歸：時間複雜度 O(k^n)，空間 O(n) 棧深度
static int fib_k(int n, int k) {
    if (n < k) return 1;
    int result = 0;
    for (int i = 0; i < k; i++) {
        result += fib_k(n - i - 1, k); // 大量重複子問題
    }
    return result;
}

當 k=4, n=20 時，遞歸樹呈指數增長，運行時間明顯可感。

二、動態規劃優化：自底向上填表

// 優化版：時間 O(n*k)，空間 O(n)
static int fib_k_optimize(int n, int k) {
    if (n < k) return 1;
    int[] fib = new int[n + 1];
    for (int i = 0; i < k; i++) fib[i] = 1; // 初始化前 k 項
    for (int i = k; i <= n; i++) {
        int result = 0;
        for (int j = 0; j < k; j++) {
            result += fib[i - j - 1]; // 直接查表，無重複計算
        }
        fib[i] = result;
    }
    return fib[n];
}

核心思想：空間換時間，用數組緩存所有子問題結果，消除重複遞歸調用。

三、性能對比實測

public static void main(String[] args) {
    // 朴素遞歸
    long start = System.nanoTime();
    for (int i = 0; i < 20; i++) System.out.print(fib_k(i, 4) + " ");
    System.out.println("\n朴素遞歸耗時: " + (System.nanoTime() - start) + " ns");

    // 優化版
    start = System.nanoTime();
    for (int i = 0; i < 20; i++) System.out.print(fib_k_optimize(i, 4) + " ");
    System.out.println("\n動態規劃耗時: " + (System.nanoTime() - start) + " ns");
}

典型輸出（納秒級）：

朴素遞歸耗時: 12,345,678 ns
動態規劃耗時: 45,678 ns
// 性能提升超 200 倍！

四、進一步優化方向

1. 滾動數組降維：僅保留最近 k 個值，空間從 O(n) 降至 O(k)。
2. 矩陣快速冪：對於固定 k，可構造轉移矩陣，將時間降至 O(k^3 log n)。
3. 記憶化遞歸：保留遞歸結構，配合 Map 緩存，自頂向下同樣達到 O(n*k)。

五、總結

遞歸優化的本質是識別重疊子問題 + 緩存結果。動態規劃（自底向上）與記憶化遞歸（自頂向下）是兩大通用技術。面對遞歸性能瓶頸，先畫遞歸樹分析重複度，再選擇合適策略，往往能獲得數量級的性能提升。