我的算法书 - 递归与记忆化：斐波那契数列

一句话算法

递归把一个问题拆成更小的同类问题，记忆化把算过的子问题存起来避免重复计算。

问题模型

斐波那契数列定义为：

F(1)=1,\quad F(2)=1

当 $n \ge 3$ 时：

F(n)=F(n-1)+F(n-2)

要求输入 n，输出 F(n)。

核心直觉

计算 F(n) 时，只要知道 F(n-1) 和 F(n-2)。

所以可以把大问题拆成两个小问题：

F(n)
├── F(n-1)
└── F(n-2)

但普通递归会反复计算同一个子问题。例如 F(5) 会算 F(3)，F(4) 里面又会再算一次 F(3)。

记忆化的想法很直接：第一次算出 F(i) 后放进数组，后面再遇到 F(i) 就直接返回。

算法步骤

普通递归

如果 n == 1 或 n == 2，返回 1。
否则返回 fibonacci(n - 1) + fibonacci(n - 2)。

记忆化递归

如果 n == 1 或 n == 2，返回 1。
如果 memo[n] 已经有值，直接返回 memo[n]。
否则递归计算答案，保存到 memo[n]，再返回。

算法证明

普通递归直接照搬斐波那契定义。

边界 F(1)、F(2) 返回 1，与定义一致。
对于 n >= 3，算法返回 F(n-1) + F(n-2)，与递推式一致。
每次递归都会让参数变小，最终到达边界。

记忆化不会改变答案，只改变“是否重新计算”：

如果 memo[n] 已经存在，它保存的是第一次按递推式算出的正确值。
直接返回这个值，与重新递归计算结果相同。

所以记忆化递归仍然正确。

复杂度分析

普通递归会产生大量重复子问题，时间复杂度约为 $O(2^n)$ ，递归栈空间为 $O(n)$ 。

记忆化后，每个 F(i) 只计算一次：

时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。

代码实现

普通递归

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14

        #include <bits/stdc++.h>
using namespace std;

long long fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << '\n';
    return 0;
}

记忆化递归

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 5;

long long memo[maxn];

long long fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << '\n';
    return 0;
}

测试用例

输入：

输出：

因为：

1, 1, 2, 3, 5, 8

应用分类详解

斐波那契递归的重点不是数列本身，而是“重叠子问题”。

一、递归定义清晰的问题

典型模式： 题目本身能写成“当前答案由更小规模答案组成”。

识别信号： 第 n 项、前 n-1 项、拆成若干个更小问题。

核心建模： 找出边界和递推式。

二、有重复子问题的问题

典型模式： 不同递归分支会反复访问同一个状态。

识别信号： 递归树中相同节点多次出现。

核心建模： 用数组或哈希表记录已经算过的状态。

三、动态规划入门

典型模式： 记忆化递归可以改写成从小到大的递推。

识别信号： 状态数量有限，状态之间有明确依赖关系。

核心建模： memo[i] 就是 DP 数组。

经典例题

luogu-P1255 数楼梯：斐波那契模型，但需要高精度。
leetcodecn-509 斐波那契数：递归、记忆化、递推都能练。
leetcodecn-70 爬楼梯：每次走 1 或 2 阶，本质是同类递推。

参考

本书相关章节：动态规划入门