为什么“递推”能让你从已知走向一切未知？ - 每日分享

你有没有在排队买冰淇淋的时候，无聊到开始计算前面每个人的等待时间？第一个人花两分钟，第二个人要等四分钟，第三个人六分钟……然后你突然意识到，只要知道上一个人的等待时间，加一个固定值，就能知道下一个人的。那一瞬间，排队似乎也没那么无聊了。

这种“从已知推出未知”的思考方式，在编程里叫递推。它没有递归那么玄乎，也没有动态规划那么高深，但几乎所有高效算法的基础都离不开它。今天我想借一个最经典的问题——斐波那契数列，把递推这点事讲透。

兔子、多米诺，和一条简单的规则

递推的本质就是多米诺骨牌：推倒第一块，后面每一块都会被上一块带倒。你不需要预测整排骨牌的运动轨迹，你只需要保证两件事——第一块倒了，以及相邻两块之间的距离正确。

斐波那契数列恰好就是一组完美的骨牌。它来自一个古老的兔子繁殖问题：一对小兔子要长大一个月才能成年，成年后每个月生一对新兔子，兔子永生。第1个月有1对幼兔，第2个月变成1对成兔，第3个月成兔生了一对，于是总共2对……你越往后数，越会发现一个规律：

这个月的兔子总数 = 上个月总数 + 上上个月总数

为什么？因为上个月的所有兔子都还活着，这是“存量”；而上上个月的兔子，到这个月全部成年，每对都会生一对新的，这是“增量”。所以：

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

就这么简单。你不需要知道第100个月怎么来的，你只需要老老实实从第3个月开始，一个月一个月往前推。

如果你觉得兔子不够贴近生活，换个场景：小明爬楼梯，每次能跨1级或2级台阶，问爬到第n级有多少种不同爬法。

第1级只有1种：跨1级。第2级有2种：1+1或者直接2。到第3级呢？你可以从第2级跨1级上来，也可以从第1级跨2级上来。所以第3级的方法数等于第2级的方法数加上第1级的方法数——又是前两项之和。数列变成了1, 2, 3, 5, 8……

注意，初始条件变了，但递推关系完全一致。这说明递推的核心价值不在于某个固定公式，而在于“当前项可以由前面若干项推算出来”这个结构性规律。学会识别这种结构，比背下斐波那契的代码重要一百倍。

很多初学者第一次写斐波那契，喜欢开一个大数组，把每一项都存下来。完全没问题，但没必要。因为我们只需要最后一项，而计算下一项时只用得到前两项。用三个变量滚动更新就够了：

int a = 1, b = 1;   // 第1项，第2项
int cur = 1;

for (int i = 3; i <= n; ++i) {
    cur = a + b;    // 先算当前项
    a = b;          // 再更新前两项
    b = cur;
}

这里有个容易踩的坑：更新顺序不能错。有人会先写 a = b; b = cur; cur = a + b;——结果 a 已经被覆盖，算出来的 cur 完全不对。递推就像传递接力棒，必须先交接再起跑。

有这么一个题：输入一个不超过46的正整数k，输出斐波那契数列第k项。看起来太简单了，但很多人会错。

第一个关键点：第1项和第2项都是1，所以 n=1 或 n=2 时直接返回1。如果你不特判，直接跑循环，cur 根本没初始化，输出一个诡异的值。

第二个关键点：循环次数。已知两项，要推到第n项，需要算 n-2 次。如果你习惯写 for (int i = 1; i <= n; ++i)，就会多算一次，把第7项当成第6项，得到13而不是8。这是经典错误：项数错位。

多说一句，k≤46的情况下，int完全够用。但如果你把范围放大一点，比如要求第1000000项对1000取模，就又是另一道题了——

有题是这样：很多组数据，每组给一个不超过1000000的a，输出斐波那契第a项对1000取模的结果。你发现真去算第1000000项的话，数字会膨胀到天文数字，C++的整数根本装不下。

解法是：每一步都取模。因为 (a + b) % 1000 等于 (a % 1000 + b % 1000) % 1000，所以只要让每次计算都限制在1000以内，最终结果一定正确。

cur = (a + b) % 1000;
a = b;
b = cur;

这个思想超级重要：中间结果不一定要完整保留，只要不影响最终答案，就可以随手压缩。这也是很多动态规划题里“取模优化”的雏形。

回顾一下，我们从兔子问题里抽出了递推公式，从爬楼梯里看到了相同的结构，然后又解决了两个实际编程题。递推思维真正的力量在于：把一个看似无限的问题，化简为“从已知到未知”的有限步迭代。

如果你还想继续深入，有几个方向值得看看：

递归写法：F(n) = F(n-1) + F(n-2) 看上去很诱人，但一旦n变大，重复计算会爆炸。递推（循环）恰好避免了重复，这正是动态规划的基本思想。
动态规划：很多问题本质上就是“状态之间的递推”，比如背包、最长上升子序列，都是先定义好“前一项”，然后一步步推。
矩阵快速幂：当n大到10^18，循环也扛不住时，可以用矩阵乘法把递推变成幂运算，从而用快速幂在O(log n)内求出第n项。这是竞赛选手爱用的技巧。

递推是一把钥匙，打开了“从已知到未知”的门。你今天学的是兔子，明天遇到的可能是股票分析、向日葵种子排列、搜索引擎的排名算法——背后全是同一个思维模型。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）