F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)
數列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
#include <stdio.h>
int Fibonacci(int n) {
if (n <= 1) return n; // 基底情況：F(0)=0, F(1)=1
return Fibonacci(n-1) + Fibonacci(n-2);
}
int main() {
int n;
printf("請輸入 n: ");
scanf("%d", &n);
printf("F(%d) = %d\n", n, Fibonacci(n));
return 0;
}遞迴版本產生指數級呼叫樹：
F(5)
├─ F(4)
│ ├─ F(3)
│ │ ├─ F(2)
│ │ │ ├─ F(1)
│ │ │ └─ F(0)
│ │ └─ F(1)
│ └─ F(2)
│ ├─ F(1)
│ └─ F(0)
└─ F(3)
├─ F(2)
│ ├─ F(1)
│ └─ F(0)
└─ F(1)時間複雜度 O(2^n)，空間複雜度 O(n) (遞迴堆疊深度)。n=40 即明顯延遲，n=50 極慢。
| 方法 | 時間複雜度 | 空間複雜度 | 備註 |
|---|---|---|---|
| 遞迴 + 備忘錄 (Memoization) | O(n) | O(n) | 陣列/雜湊表快取已計算值 |
| 動態規劃 (迭代自底向上) | O(n) | O(1) | 僅保留前兩值，**工程首選** |
| 矩陣快速冪 | O(log n) | O(1) | 大數值、競程常用 |
| 通項公式 (Binet 公式) | O(1) | O(1) | 浮點精度限制，大 n 不準 |
int FibonacciIter(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) {
c = a + b;
a = b;
b = c;
}
return b;
}int 32 位元有號最大 2,147,483,647，F(46)=1,836,311,903、F(47) 溢位。需用 unsigned long long (64 位元，至 F(93)) 或大整數庫 (GMP, Boost.Multiprecision)。
遞迴版本雖低效，但完美展示「分治」與「重疊子問題」特性，是動態規劃教學的經典切入點。
