你好，我是林森 lsjs
我的Github 地址：sqyCoder (Qiyang) · GitHub
以博文记录成长，用心打磨代码与思维
今天拿经典的斐波那契数列开刀。
几乎所有学递归的同学，第一道例题都是斐波那契。一行递归代码就能写出来
很多人觉得 “这也太简单了”。
但你有没有试过输入 n=45？程序跑半天出不来结果
从暴力递归到最优的 O (1) 空间解法，中间到底经历了哪些优化思考？
今天我们一步步拆解
目录
一、先明确：斐波那契数列的定义
二、解法一：暴力递归（最直观，但也最慢）
1. 思路与代码实现
2. 递归树展开：为什么会这么慢
三、解法二：记忆化搜索（递归版优化，加备忘录）
1. 优化核心：解决重叠子问题
2. 完整代码实现
3. 复杂度与遗留问题
四、解法三：动态规划（迭代版，自底向上）
1. 从自顶向下到自底向上
2. 三要素
3. DP 数组完整代码
复杂度分析
五、3 个坑点
坑 1：数据溢出
坑 2：边界条件混乱
坑 3：递归深度溢出
六、四种解法横向对比
七、总结
一、先明确：斐波那契数列的定义
先统一定义，避免歧义
不同教材的起点不一样，有的从第 1 项开始算，有的从第 0 项开始，我们全文统一标准：
第 0 项：F (0) = 0
第 1 项：F (1) = 1
递推公式（n ≥ 2）：F (n) = F (n-1) + F (n-2)
简单说就是：从第三项开始，每一项都等于前两项之和。
我们的目标是，输入整数 n，输出第 n 项斐波那契数的值。
二、解法一：暴力递归（最直观，但也最慢）
1. 思路与代码实现
这是所有人入门的第一版写法，完全照着数学递推公式翻译代码。核心逻辑是自顶向下拆解：
想算出 F (n)，就得先算出 F (n-1) 和 F (n-2)；想算 F (n-1)，就得先算 F (n-2) 和 F (n-3)……
层层拆解，直到触达 F (0) 和 F (1) 这两个已知的终止条件，再一层层把结果加回来。
// 解法一：暴力递归
public int fib(int n) {
// 递归终止条件：触达基础项，直接返回已知值
if (n == 0) return 0;
if (n == 1) return 1;
// 按递推公式，拆解为两个子问题，递归求解后相加
return fib(n – 1) + fib(n – 2);
}
2. 递归树展开：为什么会这么慢
代码只有三行，看起来无比简洁，但性能差到离谱。我们把 fib (5) 的递归调用树展开，问题一目了然：
fib(5)
/ \\
fib(4) fib(3)
/ \\ / \\
fib(3) fib(2) fib(2) fib(1)
/ \\
fib(2) fib(1)
光是 fib (3) 就被重复计算了 2 次，fib (2) 被算了 3 次。n 越大，重复计算的量就呈指数级爆炸：
n=10：总共调用 89 次函数
n=20：总共调用 10946 次函数
n=30：总共调用 134 万次函数
n=40：总共调用一亿多次函数
这就是指数级增长的恐怖之处。
n 到 45 的时候，普通电脑要跑好几秒；n 到 50，基本就要等几分钟了，完全无法投入实际使用。
三、解法二：记忆化搜索（递归版优化，加备忘录）
1. 优化核心：解决重叠子问题
既然重复计算是问题，那优化思路也很直接：算过的结果存起来，下次再用直接拿，不重复算。
这就是”备忘录“思想，也叫记忆化搜索。
我们用一个数组当缓存（备忘录），下标对应 n，值存 F (n) 的结果。每次递归前先查缓存：
算过就直接返回，没算过就算完存进去再返回。
这背后对应动态规划的第一个核心特性：重叠子问题—— 一个大问题可以拆成很多小问题，而很多小问题是完全重复的。
2. 完整代码实现
// 解法二：记忆化递归（备忘录法）
public int fib(int n) {
// 备忘录数组，长度n+1，存0~n所有项的结果
// 用-1初始化，表示这个位置还没算过
int[] memo = new int[n + 1];
for (int i = 0; i <= n; i++) {
memo[i] = -1;
}
return dfs(n, memo);
}
private int dfs(int n, int[] memo) {
// 终止条件
if (n == 0) return 0;
if (n == 1) return 1;
// 核心：先查备忘录，已经算过就直接返回，不递归
if (memo[n] != -1) {
return memo[n];
}
// 没算过：递归计算，结果存入备忘录，再返回
memo[n] = dfs(n – 1, memo) + dfs(n – 2, memo);
return memo[n];
}
细节说明：为什么不用 0 初始化？因为 F (0)=0，如果用 0 代表 “未计算”，那第 0 项就会被误判成没算过，重复计算。用 – 1 标记未计算状态，逻辑更严谨。
3. 复杂度与遗留问题
时间复杂度：O (n) 每个 n 只算一次，没有重复计算，直接从指数级降到线性级
空间复杂度：O (n) 备忘录数组占 n+1 的空间，再加上递归栈的深度 n
加了一个缓存数组，性能直接提升了几个数量级，n=10000 也能瞬间出结果。这就是算法优化的威力。
但它依然有遗留问题：
四、解法三：动态规划（迭代版，自底向上）
1. 从自顶向下到自底向上
记忆化递归是自顶向下：
从目标 n 出发，一层层拆到基础项，边算边存。
动态规划是自底向上：从已知的 F (0)、F (1) 出发，按照递推公式，一步步往前推，直到算出我们要的 F (n)。
整个过程完全不用递归，用循环迭代就能完成，彻底摆脱递归栈的限制。
2. 三要素
所有动态规划题，都可以拆成三个核心要素，套这个框架就不会乱：
把这三点想清楚，代码就自然而然写出来了。
3. DP 数组完整代码
// 解法三：动态规划 DP数组版
public int fib(int n) {
// 边界特殊处理：n=0时数组长度为1，不会越界
if (n == 0) return 0;
// 1. 定义dp数组：dp[i] 表示第i项斐波那契数
int[] dp = new int[n + 1];
// 2. 初始化基础状态
dp[0] = 0;
dp[1] = 1;
// 3. 从第2项开始，自底向上递推
for (int i = 2; i <= n; i++) {
// 状态转移方程
dp[i] = dp[i – 1] + dp[i – 2];
}
return dp[n];
}
复杂度分析
时间复杂度：O (n) 一次循环遍历，线性时间
空间复杂度：O (n) DP 数组占用线性空间
没有递归栈风险，运行稳定，逻辑清晰 —— 这是最标准、最容易理解的动态规划入门写法。
很多同学觉得 DP 难，其实它的本质就是记住算过的结果，避免重复计算，和记忆化搜索是同一个核心，只是实现方向反过来了。
五、3 个坑点
坑 1：数据溢出
int 只能撑到第 46 项，long 撑到第 92 项。题目没说明的情况下，要么用 long，要么按要求取模，别等结果变负数了才反应过来溢出了。
坑 2：边界条件混乱
一定要看清题目是从 0 开始还是从 1 开始。比如有的题定义 F (1)=1、F (2)=1，那循环就要从 i=3 开始，初始化也要对应调整，差一位全错。
坑 3：递归深度溢出
暴力递归和记忆化递归都受栈深度限制，n 超过几千就可能栈溢出。大规模数据一定用迭代版，别头铁用递归。
六、四种解法横向对比
我把四种解法的核心信息整理成了表格，一目了然：
| 暴力递归 | O(2ⁿ) | O (n)（递归栈） | 按公式自顶向下拆解 | 写法最简单，但效率极低，n 稍大就无法运行，有栈溢出风险 |
| 记忆化搜索 | O(n) | O (n)（备忘录 + 递归栈） | 缓存重复计算结果 | 解决了重复计算，但仍有递归栈开销，大数量级不稳定 |
| DP 数组 | O(n) | O(n) | 自底向上迭代计算 | 稳定高效，无递归风险，逻辑最清晰，是动态规划标准写法 |
七、总结
整条优化路径，也是算法优化的通用思考路线：
很多同学觉得动态规划难，其实它的本质就是 记住算过的结果，避免重复计算。
从记忆化递归过渡到 DP 数组，是最自然、最容易理解的学习路径。
斐波那契虽然简单，但它浓缩了整个动态规划的核心思想，把它吃透，后面学背包、路径问题都会轻松很多。
诸位共勉，无限学习！
