Fibonacci

一句话理解

Fibonacci：F(1)=F(2)=1，后面每一项是前两项之和。

为什么要学

递归入门、DP 入门、矩阵快速幂都会拿它练。

讲解

朴素递归指数级慢。线性递推 O(n)，再往后可以矩阵加速。

先写对递归，再改循环，体会“同一转移，两种实现”。

例子

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

fib(5)=fib(4)+fib(3)=3+2=5。定义因题目可能从 0 起，要看清 F(0) 是不是 0。

常见错误

• 边界写成 n==0 返回 1 却有人问 F(0)=0。
• n=40 还用朴素递归，会很慢。