递推关系式：像搭积木一样一步步解决问题

你有没有试过玩多米诺骨牌？推倒第一张，后面的牌就会一张接一张倒下。递推关系式就像这样：只要知道了最开始几块牌的状态，再按照固定的规则，就能知道后面每一块牌的样子。在编程里，我们用递推关系式来解决那些“一步接一步”的问题——比如计算爬到第10级楼梯有多少种走法、预测第100天攒了多少零花钱。

1. 什么是递推关系式？

递推关系式 是一个数学公式，它用前面一个或几个结果来算出后面的结果。就像你站在楼梯上，想知道爬到第 n 级有多少种方法，只要知道爬到前几级的方法数，就能推算出来。

还记得「魔法楼梯」吗？

走到第1级：只能从地面走1步 → 1种方法
走到第2级：可以一次走2级，或者走两次1级 → 2种方法
走到第3级：你只能从第1级跨2步，或者从第2级跨1步。所以方法数 = 第1级方法数 + 第2级方法数 = 1 + 2 = 3

这个规律一直成立：
爬到第 n 级的方法数 = 爬到第 n-1 级的方法数 + 爬到第 n-2 级的方法数

把这句话写成数学符号就是：

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

这就是递推关系式。你只需要记住“起始值”（第1级和第2级）和“递推规则”，就能算出所有台阶。

2. 生活中的递推例子（比吃零食还简单！）

除了爬楼梯，很多日常现象都藏着递推规律：

例1：零花钱增长

小明的妈妈给他一个“每周涨1元”的约定：第1周给5元，以后每周比上一周多给2元。

第1周：5元
第2周：5 + 2 = 7元
第3周：7 + 2 = 9元
递推式：零花钱(周) = 零花钱(周-1) + 2，起始 零花钱(1) = 5

例2：考试复习题量

小红每天做数学题，第一天做3道，之后每天比前一天多做4道。

第1天：3道
第2天：3 + 4 = 7道
第3天：7 + 4 = 11道
递推式：题量(天) = 题量(天-1) + 4，起始 题量(1) = 3

例3：排队买冰淇淋（原例子升级）

冰淇淋店每1分钟来2个新顾客，一开始有3个人在排队。

第0分钟：3人
第1分钟：3 + 2 = 5人
第2分钟：5 + 2 = 7人
递推式：人数(t) = 人数(t-1) + 2，起始 人数(0) = 3

这些例子虽然简单，但都体现了同一个思想：已知开始，用固定规则往后推。

3. 如何用Python写出递推？—— 三步法

写递推程序就像搭积木，三个步骤：

确定初始值（搭地基）
写出递推公式（规则）
循环或列表存储中间结果（一块块往上搭）

我们依然用爬楼梯的例子，但这次写得更细致些，并加上详细的注释。

def climb_stairs(n):
    """
    计算爬到第n级楼梯有多少种走法（每次可以走1级或2级）
    """
    # 如果楼梯少于3级，直接返回已知结果
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # 创建一个列表来存储每一级的结果，下标从0开始
    # 为了阅读方便，我们让下标i表示第i级的结果
    dp = [0] * (n + 1)      # dp是列表名字，代表“每一步的结果”
    dp[1] = 1               # 第1级：1种方法
    dp[2] = 2               # 第2级：2种方法
    
    # 从第3级开始，用递推公式计算出结果
    for step in range(3, n + 1):
        dp[step] = dp[step - 1] + dp[step - 2]   # 递推核心公式
    
    return dp[n]

# 测试：输出从第1级到第10级的方法数
for level in range(1, 11):
    result = climb_stairs(level)
    print(f"爬到第{level}级有{result}种方法")

运行结果：

爬到第1级有1种方法
爬到第2级有2种方法
爬到第3级有3种方法
爬到第4级有5种方法
爬到第5级有8种方法
爬到第6级有13种方法
爬到第7级有21种方法
爬到第8级有34种方法
爬到第9级有55种方法
爬到第10级有89种方法

解释代码细节：

dp 是一个列表，用来存放每一级的结果，就像一张草稿纸，记下算过的数字。
循环从 step = 3 开始，因为前两级已经填好了。每次循环，新的结果由前两个结果相加得到。
最后 return dp[n] 就是第 n 级的结果。

4. 新手最容易犯的错误

初学递推时，下面几个坑可要小心避开：

错误1：忘记初始化第一、二个值

dp = [0] * (n + 1)
# 忘了写 dp[1] = 1 和 dp[2] = 2
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]   # dp[1]和dp[2]是0，结果全错

正确做法：一定要先给“地基”赋值。

错误2：索引越界

如果递推式用到 dp[i-2]，但 i 从 2 开始，那么 dp[0] 可能没有定义。比如爬楼梯例子中，如果 n=1 直接返回， n=2 直接返回，就不会用到 dp[0]。但如果你把 n 设得太小，或者循环范围写错，就可能出错。

错误3：混淆递推和递归

递推是用循环从前往后算；递归是函数自己调用自己，从后往前拆分。初学者容易写成递归但忘记终止条件，导致无限循环。
小贴士：能用递推解决的问题，尽量用递推（效率高），写代码时用循环+列表。

错误4：列表大小不够

dp = [0] * n      # 如果n=10，列表只有10个元素，下标0~9
dp[1] = 1         # 没问题，但dp[10]不存在

正确做法：dp = [0] * (n + 1) 确保下标从0到n都能用。

5. 完整可运行的示例：零花钱增长

来看一个完整的例子，计算第 n 周小明有多少零花钱（第1周5元，每周增加2元）。

def pocket_money(week):
    """
    计算第 week 周的零花钱（单位：元）
    递推公式：money(w) = money(w-1) + 2，初始 money(1) = 5
    """
    if week < 1:
        return 0
    
    # 创建列表存放每周结果，下标从0开始
    money = [0] * (week + 1)    # money列表名，意为“钱”
    money[1] = 5                # 第1周有5元
    
    # 从第2周开始递推
    for w in range(2, week + 1):
        money[w] = money[w - 1] + 2   # 每周多2元
    
    return money[week]

# 输出前10周的零花钱
for w in range(1, 11):
    print(f"第{w}周有{pocket_money(w)}元")

输出：

第1周有5元
第2周有7元
第3周有9元
第4周有11元
...
第10周有23元

6. 相关知识点指引

学会了递推关系式，你还可以接着学习：

递归：递推的“逆向”版，从结果反推到初始条件。适合解决“分解子问题”的问题，比如汉诺塔、阶乘。
动态规划：递推的“升级版”，专门解决最优化问题（比如最短路径、最大收益）。动态规划的核心思想和递推一模一样：找初始值 + 递推公式。
斐波那契数列：数学中经典的递推例子，和爬楼梯本质相同。
使用一维/二维数组：当问题变得复杂（比如迷宫、背包问题），你需要用二维甚至三维列表来存储中间结果，这正是递推的扩展。

想挑战一下自己？试试下面这个有趣的问题：

小明攒了50元零花钱，他想买一个200元的玩具。如果他每周再得到12元零花钱，并且每周花掉5元买零食，那么多少周后他能买得起玩具？
（提示：用递推式模拟每周剩余的钱）

把你写出来的代码和同学一起跑跑看，你会发现递推就像搭积木——垒好第一块，后面的自然就盖起来了！

Python递推关系式的推导