遞歸數列求值：F[19] + F[13] 計算與遞歸優化探討

數列定義

已知遞歸數列：
F[1] = 1, F[2] = 1, F[3] = 5,
F[n] = F[n-1] + 2 × F[n-2] (n ≥ 3)
求 F[19] + F[13] 的值。

遞歸實現與缺陷

int fun(int n) {
    if (n <= 2) return 1;
    return fun(n-1) + 2 * fun(n-2);
}

直接遞歸存在大量重複計算，時間複雜度呈指數級增長。雖然 n=19 仍可在短時間內跑完，但屬於典型的「重疊子問題」。

優化方案：記憶化 / 動態規劃

方法一：記憶化遞歸（自頂向下）

int memo[20] = {0};
int fun_memo(int n) {
    if (n <= 2) return 1;
    if (memo[n]) return memo[n];
    return memo[n] = fun_memo(n-1) + 2 * fun_memo(n-2);
}

方法二：迭代 DP（自底向上，空間 O(1)）

int fun_dp(int n) {
    if (n <= 2) return 1;
    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = b + 2 * a;
        a = b;
        b = c;
    }
    return b;
}

計算結果

F[13] = 2731, F[19] = 174763, 兩者之和為 177494。

總結

理解遞歸定義是基礎，識別重疊子問題並應用記憶化或 DP 是進階關鍵。本題數據範圍小，但思想具備通用性。