递推，编程里那块最被低估的万能积木
编程里最强大的思想，往往不是那些高深的算法，而是像递推这样朴素到容易被忽略的思维方式。它不需要你懂什么数学天赋，也不涉及复杂的数据结构——只要你能回答两个问题：起点是什么？下一步怎么走？ 接下来，计算机就能替你完成所有重复劳动。
很多人第一次听说“递推”，是在一道“兔子繁殖”的题里。但实际上，它早就在你的生活里反复出现。比如你每天爬楼梯：从 1 楼出发，每次上 1 层。那么你的状态变化就是：
1 楼 → 2 楼 → 3 楼 → ...
每一次的新位置 = 旧位置 + 1。这就是递推。在代码里，递推的骨架永远是同一个循环模式：
current = initial
while 还没结束:
next_value = 根据规律(current)
current = next_value
这里的关键动作，是每次算完新值后，把新值变成旧值。很多人写不好递推，就是在这一步掉了链子。
一、递推关系式：那把“钥匙”
递推关系式，是告诉你“怎么从前面的结果得到后面的结果”的规则。它像一把钥匙，有了它，计算机才能自动往下算。
比如数列：
3, 6, 9, 12, 15, ...
观察相邻两项的差，全是 3。所以递推关系是：
第 n 项 = 第 n-1 项 + 3
初始条件：第 1 项 = 3
但如果给你：
1, 4, 9, 16, 25, ...
这是平方数，每一项直接等于 n*n。注意，它没有使用前一项，所以严格说不是递推关系式。不过，你可以换个角度：相邻两项的差是 3, 5, 7, 9...（连续奇数），于是也能写成：
第 n 项 = 第 n-1 项 + (2n-1)
这样它就变成了递推。
新手最容易犯的一个错误，是看到一个数列就急着找“通项公式”，结果写出来的式子根本不依赖前一项。记住，递推必须有前一项或前几项的参与。
有一道经典题，专门考察这种构造递推的能力：
输入一个自然数 n。允许在它的左边加上一个不超过原数一半的自然数，然后对新数继续做同样的操作，直到不能再加为止。问一共能得到多少个数？
比如 n=6，能产生 6, 16, 26, 36, 126, 136 ... 这样的数。直接枚举很容易乱，但递推却很简单。
设 f[i] 表示以数字 i 为“基础”时，能产生的数的总数。根据规则，i 本身算一个；它的左边可以加上 1 到 i//2 中的任意一个数 j，加完之后，新数字还能继续产生 f[j] 个结果。于是递推关系式就出来了：
f[i] = 1 + sum(f[1] + f[2] + ... + f[i//2])
初始条件 f[1] = 1，因为数字 1 左边不能加任何数，只有它自己。
代码很短：
n = int(input())
f = [0] * (n + 1)
for i in range(1, n + 1):
f[i] = 1 + sum(f[1 : i // 2 + 1])
print(f[n])
这道题最妙的地方在于，你不需要真的“构造出”那些数，只要找到数量之间的递推关系，剩下的交给循环。这就是递推的威力——从结果的角度思考问题，而不是模拟过程。
二、斐波那契：递推的经典名片
如果说递推有一座圣殿，那必然是斐波那契数列。
兔子问题的版本很多，但核心是同一个故事：一对刚出生的兔子，第二个月成熟，第三个月开始每月生一对，问第 n 个月有多少对兔子。得到的数列是：
1, 1, 2, 3, 5, 8, 13, 21, ...
从第三项开始，每一项等于前两项之和：
F(n) = F(n-1) + F(n-2)
F(1) = 1, F(2) = 1
代码只需要三个变量：
a, b = 1, 1
for i in range(3, 21):
c = a + b
a, b = b, c
print(c)
这里要特别提醒：递推关系里的运算符号绝不能想当然。加法、乘法、减法看起来都“像”，但结果天差地别。斐波那契的递推是加法，因为每月的兔子数等于前两个月之和。如果你写成乘法或减法，数列很快就不成立了。
这也是很多选择题爱挖的坑：问斐波那契的递推关系，四个选项分别写 +1、前两项之和、前两项之积、前两项之差。只要抓住定义——从第三项开始，每一项等于前两项之和——就不会错。
三、新手最容易踩的三个坑
我见过太多人栽在下面这三件事上，每一个都值得写成血泪教训。
坑 1：忘记更新旧变量
first = 1
for i in range(1, 10):
next_number = first + 1
print(next_number)
# 忘写了 first = next_number
这段代码会一直输出 2，因为你永远在用旧值 first=1 算新值，没有把新值“转移”成旧值。递推的核心就是滚动更新，这一步是灵魂。
坑 2：初始条件错了
比如斐波那契，如果你把初始条件写成 F(1)=0, F(2)=1，整个数列就变成了 0,1,1,2,3... 虽然看起来也像，但那是另一个数列了。每个递推问题都像开锁，钥匙孔必须对准。初始条件就是你插入锁孔前的那次定位——对不上，后面全白费。
有一个判断题说得很对：递推算法在求解问题时，必须明确初始条件（边界值）。 这句话是对的。因为递推关系式只是一条规则，没有初始条件，它无从启动。好比计算阶乘，n! = n × (n-1)!，但如果没人告诉你 0! = 1，这个递推就永远跑不起来。
坑 3：递推关系式写错
这个更隐蔽。有时候你觉得自己找到了规律，但算前两项就露馅了。我的建议是：写完后，先手动算三个例子，看结果是否符合预期。验证是程序员的本能，别偷懒。
四、一个活生生的例子：存钱罐
来一个完整的训练。第一天存 1 元，之后每天比前一天多存 1 元。问第 10 天存了多少、总共存了多少。
这其实是两个递推在并行：
- 当天存的钱：
today = today + 1 - 总共存的钱：
total = total + today
days = 10
today = 1 # 第一天存的钱
total = 0 # 总金额
for day in range(1, days + 1):
total += today
print(f"第{day}天：当天存{today}元，总共存{total}元")
today += 1 # 明天的钱基于今天的钱推出
这个程序虽小，却包含了递推的全部要素：起点（第一天存 1 元）、规律（每天 +1）、重复执行（for 循环）。把它改成 100 天，也就是改一个数字的事。
五、递推之后，通向哪里？
递推本身不复杂，但它是一把钥匙，打开很多看似高大上的门。
- 递归：和递推正好相反。递推是从边界出发，往前推；递归是从目标出发，往回调用自己。很多递归问题（比如斐波那契）改成递推后效率更高，不会爆栈。
- 动态规划：递推是动态规划的雏形。动态规划本质上就是“带状态的递推”，只不过多了“最优子结构”“重叠子问题”这些讲究。
- 数学归纳法：递推的数学根基。你用递推解决问题的过程，其实就是在证明：第一步成立，假如第 k 步成立，那么第 k+1 步也成立。
所以，别觉得递推是个小知识点。你把它吃透了，后面学递归、学动态规划，都会有一种“原来你也在这里”的亲切感。
递推就是编程里的积木——底层只有一块，但只要你找到规律，就能一块接一块地搭出无限可能。下次再遇到“第一天……之后每天都……”这种问题，别忘了你手里有这块万能积木。
关于作者
我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。
这些年累计帮助 多名 学生通过编程特长升入自己心仪的目标学校。
如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）