目錄

什么是斐波那契數列？

用遞歸推導Fibonacci

復雜度分析

?用迭代推導Fibonacci

?復雜度分析

?遞歸優化：記憶化遞歸（Memoized Recursion）?

復雜度分析

---

什么是斐波那契數列？

斐波那契數列（Fibonacci Sequence）是這樣一個序列：

從第 2 項開始，每一項等于前兩項之和。

F(0) = 0
F(1) = 1
F(2) = 1        ← 0 + 1
F(3) = 2        ← 1 + 1
F(4) = 3        ← 1 + 2
F(5) = 5        ← 2 + 3
F(6) = 8        ← 3 + 5
F(7) = 13       ← 5 + 8
F(8) = 21       ← 8 + 13
...

---

用遞歸推導Fibonacci

我們用自然語言重新表述遞歸的核心思想：

要計算第 n 項，只需遞歸調用第 n?1 項和第 n?2 項的計算，直到我們知道結果的那一刻（也就是 n==0 或 n==1）為止。

所以遞歸的思想是：

1. 邊界條件（Base Case）：當 n == 0 或 n == 1，直接返回 n 本身。

2. 遞歸調用：否則，就返回 fib(n - 1) + fib(n - 2)。

int fib(int n) {if (n <= 1) return n;         // base casereturn fib(n - 1) + fib(n - 2); // recursion
}

復雜度分析

我們以 fib(5) 為例，畫出調用樹結構?

                      fib(5)/      \fib(4)        fib(3)/     \        /     \fib(3)     fib(2)  fib(2)  fib(1)/     \     /   \   /   \fib(2)   fib(1) fib(1) fib(0) fib(1)/   \
fib(1) fib(0)

📈 時間復雜度?

T(n) = T(n-1) + T(n-2) + O(1)

其中：

• T(n-1)：遞歸求 fib(n-1)

• T(n-2)：遞歸求 fib(n-2)

• O(1)：加法操作 + 1 次返回?

?所以 T(n) 的增長趨勢就是 Fibonacci 的大小增長趨勢，即：

T(n) ≈ O(2?)

🔍 你可以這么理解這個復雜度

在最差情況下，調用樹是一個二叉樹：

• 高度：n

• 節點數 ≈ 2?（滿二叉樹）

• 每個節點代表一次函數調用 → 所以總時間就是 O(2?)

?故時間復雜度是 O(2?)

復雜度	說明
時間復雜度	O(2?)，因為調用樹呈指數爆炸，每次展開兩個分支
空間復雜度	O(n)，因為遞歸棧最深可達 n 層

---

?用迭代推導Fibonacci

核心問題：如何“推進到下一步”？

我們寫下第一項和第二項：?

step 0: 0   → 這是 F(0)
step 1: 1   → 這是 F(1)

從 step 2 開始，每一步我們都：

1. 把上面兩個數加起來，得出當前項

2. 把這兩個數“往前移動”，以備下一次使用

因此，我們要用變量表示這個“移動窗口”，讓它們“滑動”到下一項：（有點類似于SQL中的窗口滑動）

我們只要兩個變量：

a = 0;   // 表示 F(n - 2)
b = 1;   // 表示 F(n - 1)

我們用第三個變量：

next = a + b;  // 當前項 F(n)

之后我們把窗口向前滑動：

a = b;
b = next;

?這三步形成了一個“更新循環”。

完整代碼：

思考邏輯結構

• 需要處理：

  • n == 0：返回 0

  • n == 1：返回 1

• 從 i = 2 開始循環，到 i == n

• 使用變量 a, b, next 來存儲 F(n-2), F(n-1), F(n)

#include <iostream>
using namespace std;int fib_iterative(int n) {if (n == 0) return 0;  // 基礎情況if (n == 1) return 1;  // 基礎情況int a = 0;  // 表示 F(0)int b = 1;  // 表示 F(1)int next;   // 用來存當前項 F(n)for (int i = 2; i <= n; ++i) {next = a + b;  // 當前項a = b;         // 向前滑動b = next;      // 向前滑動}return next;  // 最終 next 是 F(n)
}

?復雜度分析

??時間復雜度（Time Complexity）

看看上面這段代碼里，哪些操作會隨著 n 增長而重復？

• for (int i = 2; i <= n; ++i)
  這個循環會執行 (n - 1) 次（從 i=2 到 i=n）

• 每次循環內，做了以下操作：

  • next = a + b;

  • a = b;

  • b = next;

這些都是常數時間操作，每次循環都執行固定次數。

? 結論：

• 循環執行 n - 1 次，每次是 O(1)

• 所以：時間復雜度為 O(n)

🗃?空間復雜度（Space Complexity）?

我們在函數中定義了：

• int a = 0;

• int b = 1;

• int next;

無論 n 多大，我們始終只使用這 3 個變量來計算 Fibonacci 數列。

我們沒有使用數組、沒有遞歸棧，也沒有任何隨著 n 增長而變大的數據結構。

? 結論：

• 內存使用是常數級別

• 所以：空間復雜度為 O(1)

---

?遞歸優化：記憶化遞歸（Memoized Recursion）?

在遞歸實現中，你會發現一個規律：很多調用是重復的！

例如在fib(5)中：

• fib(3) 被調用了 2 次

• fib(2) 被調用了 3 次

• fib(1) 被調用了 5 次

這就是遞歸 Fibonacci 的最大問題 —— 重疊子問題！這是一種指數級的浪費。

? 第一性解法：我們應該記住已經算過的結果。?

💡如何實現“記住”？

我們用一種最基本的數據結構 —— 數組，開一個數組 memo[] 存儲結果。

邏輯流程：

我先檢查 memo[n] 是否已經存有值：

• 如果有，就直接返回它；

• 如果沒有，就計算出來，并把結果存進去。

一步一步改造原始遞歸函數

原始遞歸（無記憶）：

int fib(int n) {if (n == 0) return 0;if (n == 1) return 1;return fib(n - 1) + fib(n - 2);
}

? 加入“備忘錄數組”（記憶）

const int MAX = 1000;
int memo[MAX];  // 初始化為 -1 表示未計算void init_memo() {for (int i = 0; i < MAX; ++i) {memo[i] = -1;}
}int fib(int n) {if (memo[n] != -1) return memo[n];  // 如果已經算過了if (n == 0) return memo[0] = 0;if (n == 1) return memo[1] = 1;// 沒算過，就遞歸計算，并存入 memomemo[n] = fib(n - 1) + fib(n - 2);return memo[n];
}

剛剛實現的其實是“Top-Down 動態規劃”

雖然我們沒有提任何術語，但你用的是一種“從上往下遞歸，同時緩存子結果”的方法。

如果你用迭代而非遞歸，那就是“Bottom-Up 動態規劃”。

復雜度分析

項目	原始遞歸	記憶化遞歸
時間復雜度	O(2?)（指數級）	O(n)（每個 n 只算一次）
空間復雜度	O(n)（遞歸棧）	O(n)
核心優化原理	消除重復計算	每個子問題只解一次