遞歸討論（一）：階乘、費波那契與遞歸優化

遞歸討論（一）：階乘、費波那契與遞歸優化

遞歸是方法自我調用解決問題，核心在於「遞推公式」與「遞歸基」。遞歸將問題層層分解，直到達到可直接求解的基礎情況。

經典範例：階乘

數學定義：f(n) = n × f(n-1) (n≥2)，f(1)=1。代碼：

int fun(int n) { return n == 1 ? 1 : n * fun(n - 1); }

調用鏈：fun(5) → 5×fun(4) → 5×4×fun(3) → ... → 5×4×3×2×1。時間/空間複雜度均 O(n)。

費波那契數列的遞歸陷阱

定義：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。朴素遞歸：

int Fibonacci(int n) { return n <= 1 ? n : Fibonacci(n-1) + Fibonacci(n-2); }

問題：大量重複計算。F(6) 需 F(5)、F(4)；F(5) 又需 F(4)、F(3)... 時間複雜度 T(n) = T(n-1)+T(n-2) ≈ O(φⁿ) ≈ O(1.618ⁿ)，指數級爆炸。n=100 時需 2⁴⁴ 年才能算完。

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

int memo[101] = {0};
int Fib(int n) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    return memo[n] = Fib(n-1) + Fib(n-2);
}

時間複雜度降為 O(n)，空間 O(n)。

優化方案二：迭代 DP（自底向上）

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

時間 O(n)，空間 O(1)。這是工程上最優解。遞歸雖優雅，但非總是最高效——理解遞歸本質，才能在正確場合選擇正確實現。