递推法：从已知一步步算出未知，像爬楼梯一样简单

递推法是一种通过已知项逐步计算出后续项的方法。好比你要爬10级楼梯，每次可以跨1级或2级，问有多少种不同的爬法。你不需要直接想答案，而是先想第一级有几种走法，然后利用前面算好的结果，一步步推出后面的结果，直到第10级。这种“从已知推出未知”的思路，就是递推。

什么是递推？先看爬楼梯的例子

假设我们要计算爬到第 n 级台阶有多少种方法。记 f(n) 表示爬到第 n 级的方法数。

思考：要到达第 n 级，你最后一步只可能从下面两种情况来：

从第 n-1 级跨 1 步
从第 n-2 级跨 2 步

所以，爬到第 n 级的方法数就等于爬到第 n-1 级的方法数加上爬到第 n-2 级的方法数，即：

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

这就是递推公式。

还需要知道起点：

爬到第 1 级：只有 1 种方法（直接跨1步），所以 f(1)=1
爬到第 2 级：可以跨两次1步，或者一次跨2步，共2种方法，所以 f(2)=2

有了 f(1) 和 f(2)，我们就可以用公式算出 f(3)=f(2)+f(1)=2+1=3，然后 f(4)=f(3)+f(2)=3+2=5，一直算到 f(10)=89。

楼梯级数	1	2	3	4	5	6	7	8	9	10
方法数	1	2	3	5	8	13	21	34	55	89

你会发现，这个数列就是著名的斐波那契数列（从第1项开始）。递推法就像一个链条：先固定前几节，然后一节一节往后推。

递推的核心思想：用循环代替重复计算

递推和“递归”很相似，但写法不同。递归是从终点往回调用自己，容易导致重复计算，甚至栈溢出。而递推是从前往后，用一个循环依次算出每一项，并且只计算一次，效率高、内存省。

比如，用Python实现斐波那契数列（从 f(0)=0, f(1)=1 开始），递推写法就是：

def fibonacci(n):
    """返回斐波那契数列的第n项（n≥0）"""
    if n <= 1:
        return n                       # 前两项直接返回
    a, b = 0, 1                        # a表示f(0), b表示f(1)
    for i in range(2, n + 1):          # 从第2项开始递推
        a, b = b, a + b                # 同时更新：新a=老b，新b=老a+老b
    return b                          # 循环结束后b就是第n项

print(fibonacci(10))  # 输出：55

这段代码只用了两个变量，空间很小。循环执行 n-1 次，时间也很短。如果换成递归（比如 def f(n): return f(n-1)+f(n-2)），计算 f(40) 可能会卡半天，而递推瞬间出结果。

怎么找到递推公式？生活小例子帮你练手

找递推公式就像解谜，先写出前面几项，观察相邻项的关系。下面举几个贴近学生生活的例子：

例子1：存零花钱

小华每天存钱，第一天存1元，第二天存2元，第三天存3元……那么第 n 天存多少钱？其实每天存的就是 n 元，不存在递推。但如果换个规则：每天存的零花钱是前一天的两倍，第一天存1元，那么第二天存2元，第三天存4元……递推公式就是 f(n) = 2 * f(n-1)，起始 f(1)=1。用循环很容易算出第10天的钱数。

例子2：发作业本

老师发作业本，每人先发1本，然后后面每个人比前一个人多拿2本。第1人拿1本，第2人拿3本，第3人拿5本……这就是奇数序列，递推公式 f(n) = f(n-1) + 2，起始 f(1)=1。

例子3：杨辉三角

杨辉三角（也叫帕斯卡三角）中，每个数等于它上方两数之和。比如第3行的中间数是 1+2=3。如果按行递推，每一行的第一个和最后一个都是1，中间的数用上一行相邻两数之和得到。这种递推是二维的，可以用二维列表实现。

def yanghui_triangle(rows):
    """生成杨辉三角的前rows行"""
    triangle = []                     # 存放整个三角
    for i in range(rows):             # 第i行（从0开始）
        row = [1] * (i + 1)           # 所有元素先初始为1
        for j in range(1, i):         # 从第二个到倒数第二个需要计算
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)
    return triangle

# 输出前5行
for line in yanghui_triangle(5):
    print(line)

输出：

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

新手容易犯的几个错误

初始值给错
比如爬楼梯问题，f(1)=1 和 f(2)=2 很直观。但有的同学可能会认为 f(0)=0 或 f(0)=1 导致计算错误。一定要根据实际问题理解起点。
循环范围写错
斐波那契递推时，循环从 2 到 n（包括 n）。有些人写成 range(2, n) 会漏掉最后一轮，导致结果少一项。用 range(2, n+1) 才是正确的。
变量更新顺序弄反
在 a, b = b, a + b 中，Python会先计算右边 b 和 a+b 的值，再同时赋值给左边。如果你写成 a = b 然后 b = a + b，就会出错，因为 a 已经被覆盖了。所以必须用同时赋值或引入第三个临时变量。
忘记处理边界情况
比如 n=0 或 n=1 时，直接返回，不能进入循环。很多新手没加 if 判断，导致数组越界或逻辑错误。

完整可运行的代码示例：爬楼梯问题

下面给出一个完整的爬楼梯程序，输入楼梯级数，输出有多少种爬法。代码中包含详细注释。

def climb_stairs(n):
    """
    计算爬n级台阶的方法数（每次可走1级或2级）
    参数 n: 楼梯级数（n>=1）
    返回: 方法总数
    """
    if n == 1:
        return 1                      # 只有1级，1种方法
    if n == 2:
        return 2                      # 2级，2种方法

    prev1 = 1                         # 代表f(1)
    prev2 = 2                         # 代表f(2)
    current = 0                       # 存放当前计算的结果

    for step in range(3, n + 1):      # 从第3级开始递推
        current = prev1 + prev2       # f(step) = f(step-1) + f(step-2)
        prev1, prev2 = prev2, current # 为下一轮准备
    return current

# 测试
floor = 10
ways = climb_stairs(floor)
print(f"爬{floor}级楼梯共有{ways}种方法")   # 输出：89

你也可以直接输入任意级数试试。这个代码只用了三个变量，效率很高，不会因为级数大而栈溢出。

总结与相关指引

递推法是算法竞赛（CSP-J）中非常基础又重要的思想。它把大问题分解成小问题，利用已知结果逐步推进，避免了重复劳动。除了爬楼梯和斐波那契，还常用于：

汉诺塔移动步数：f(n) = 2*f(n-1) + 1
兔子繁殖（斐波那契变种）
数字三角形求路径和
卡特兰数（栈的出栈序列数）

学会了递推，你会发现很多编程题都能用“先列出递推公式，再写循环”的方法解决。如果遇到更复杂的问题（比如状态有多个维度），递推可以和动态规划结合。另外，你也可以学习记忆化递归（递归+缓存），在有些题目里写起来更直观，但效率上和递推差不多。

下一步可以尝试：

用递推法计算斐波那契数列的第100项（结果会很大，注意用Python的整数不怕）
用递推法输出杨辉三角的前10行
思考：如果爬楼梯一次可以跨1、2或3级，递推公式怎么变？

递推法：从已知逐步推出未知，像爬楼梯一样