递推
一、课上练习
编程练习
二、知识总结
✨ 递推的核心思想
递推的核心思想是：利用已知的结果，一步一步推出未知的结果。
举个生活中的例子：你在爬楼梯，每到一层楼就在纸上记下当前的楼层号。你不需要一次性知道第 100 层是多少——只要知道"上一层是第几层"，加 1 就行了。这就是递推的思路：从已知推向未知，每一步只依赖前面已经算好的结果。
在编程中，递推通常表现为一个递推公式（也叫递推关系），描述"第 n 项如何从前面的项计算得到"。例如：
- 等差数列：
a[n] = a[n-1] + d（每一项 = 前一项 + 公差） - 斐波那契数列：
f[n] = f[n-1] + f[n-2]（每一项 = 前两项之和）
✨ 递推的算法原理
递推求解的过程包含三个要素：
- 初始值：递推的起点，不能通过公式计算，必须直接给出。例如斐波那契数列的 f[0]=1, f[1]=1。
- 递推公式：描述"当前项"与"前面的项"之间的关系。例如
f[n] = f[n-1] + f[n-2]。 - 推进方向：从初始值出发，按顺序一步步向后推算，直到得到目标结果。
用循环实现递推的通用模式：
1// 第一步：设定初始值
2f[0] = 初始值;
3
4// 第二步：用循环逐步推算
5for (int i = 1; i < n; i++) {
6 f[i] = 根据递推公式，由 f[i-1] 等已知项计算;
7}
8
9// 第三步：f[n-1] 就是最终结果递推与直接计算的区别： 有些问题可以用数学公式一步算出答案（如等差数列求和公式 n*(n+1)/2），但很多问题没有这样的"万能公式"。递推的优势在于：只要能找到相邻项之间的关系，就能一步步把答案推出来，不需要知道通项公式。
常见的使用递推求解的场景有：
- 数列计算：如等差数列、等比数列、斐波那契数列等
- 贪心问题：通过局部最优推导全局最优
- 动态规划问题：通过子问题的解推导出原问题的解
目前本节课会把重点集中在数列计算上。
✨ 递推示例
等差数列
递推公式：a[n] = a[n - 1] + d
a[0] = 0;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
a[i] = a[i - 1] + d;
}等比数列
递推公式：a[n] = a[n-1] * q
a[0] = 1;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
a[i] = a[i - 1] * q;
}斐波那契数列
递推公式：f[n] = f[n-1] + f[n-2]
f[0] = 1;
f[1] = 1;
for (int i = 2; i < n; i++) { //注意当使用i - 2作为下标时，循环应该从2开始
f[i] = f[i - 1] * f[n - 2];
}✨ 递推求和
求和公式：sum(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1
递推公式：s[n] = s[n-1] + n
s[0] = 0;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
s[i] = s[i - 1] + i;
}✨ 递推求阶乘
阶乘公式：n! = n x (n - 1) x (n - 2) x ... x 3 x 2 x 1
递推公式：f[n] = f[n-1] * n
f[0] = 0;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
f[i] = f[i - 1] * i;
}✨ 递推的执行示例
以斐波那契数列为例，展示递推的完整执行过程。
问题：求斐波那契数列的前8项。
递推公式： f[n] = f[n-1] + f[n-2]，其中 f[0]=1, f[1]=1
逐步执行：
| 步骤 | i | f[i-2] | f[i-1] | 计算过程 | f[i] |
|---|---|---|---|---|---|
| 初始 | 0 | - | - | 直接赋值 | 1 |
| 初始 | 1 | - | - | 直接赋值 | 1 |
| 1 | 2 | f[0]=1 | f[1]=1 | 1+1 | 2 |
| 2 | 3 | f[1]=1 | f[2]=2 | 1+2 | 3 |
| 3 | 4 | f[2]=2 | f[3]=3 | 2+3 | 5 |
| 4 | 5 | f[3]=3 | f[4]=5 | 3+5 | 8 |
| 5 | 6 | f[4]=5 | f[5]=8 | 5+8 | 13 |
| 6 | 7 | f[5]=8 | f[6]=13 | 8+13 | 21 |
最终数列为：1, 1, 2, 3, 5, 8, 13, 21
关键观察： 每一项只依赖于前两项，所以循环必须从 i=2 开始（确保 i-1 和 i-2 都有效）。
✨ 递推的复杂度分析
递推算法的复杂度：
- 时间复杂度：O(n)，只需一次循环从头推到尾
- 空间复杂度：若使用数组存储所有中间结果则为 O(n)；若只保留前几项（如斐波那契只需前两项），可以优化到 O(1)
优点： 实现简单，效率高，避免了递归的重复计算和栈开销。 缺点： 需要找到正确的递推公式，对于某些问题递推关系不容易发现。
✨ 解题步骤详解：如何找到递推公式
遇到递推问题时，可以按照以下步骤思考：
第一步：手算前几项。 先手动计算出前4-5项的结果，观察规律。
第二步：寻找相邻项之间的关系。 思考"第n项"能否用"第n-1项"或更前面的项表示出来。
第三步：确定初始条件。 递推公式需要初始值才能开始推算，确定 f[0]、f[1] 等初始项的值。
第四步：验证公式。 用找到的递推公式重新算前几项，检查是否与手算结果一致。
举例：骨牌铺方格问题
用 1x2 的骨牌铺 2xn 的方格，有多少种方法？
- n=1：只能竖放1块，1种方法 → f[1]=1
- n=2：两块竖放或两块横放，2种方法 → f[2]=2
- n=3：在n=2的基础上竖放1块，或在n=1的基础上横放2块 → f[3]=f[2]+f[1]=3
- 递推公式：f[n] = f[n-1] + f[n-2]（和斐波那契数列相同！）
✨ 递推的常见错误
- 循环起点写错：使用 f[i-1] 时循环应从 i=1 开始，使用 f[i-2] 时应从 i=2 开始。如果从 i=0 开始，f[i-1] = f[-1] 就越界了。
- 初始值设错：例如阶乘的初始值应该是 f[0]=1（0!=1），写成 f[0]=0 会导致所有项都是0。注意原文示例中
f[0] = 0是一个需要警惕的地方，阶乘应设 f[0]=1。 - 数据溢出：递推过程中数值可能增长很快。例如阶乘增长极快，20! 就已经超过 long long 的范围。斐波那契数列第47项也会超过 int 范围。遇到大数要注意取模或使用更大的数据类型。
- 递推方向搞反：递推是从已知推向未知。如果公式是 f[n] = f[n-1] + f[n-2]，那必须从小到大计算，不能从大到小。