最近有个做后端的朋友把一段代码发过来，说程序跑了两分钟还没出结果，问我是不是电脑该换了。我扫了一眼，就是一个求第 n 个月兔子对数的递归函数，n 传的是 45。既不是死循环，也不是内存爆掉，就是那个经典到不能再经典的兔子繁殖问题——递归写法在 n 稍微大一点的时候，会以肉眼可见的速度慢下来。这事儿挺有意思，因为兔子繁殖几乎是每个人学递归时遇到的第一个例子，代码短到三行，正确性一眼就能看明白，可它同时也是最容易被写出来然后被性能按在地上摩擦的一段代码。我打算把这个题目从建模、递归推导、性能账、迭代改写一路讲到矩阵快速幂，中间夹一些我自己踩过的坑，比如起始项错位、缓存装饰器用错、大整数溢出这些看起来不起眼但真会让人调试半天的问题。不管你是刚学递归想找个练手的例子，还是工作几年了想把这块的底层逻辑重新捋一遍，下面这些内容应该都能直接用得上。

1. 兔子繁殖问题的建模：三条假设决定了一切

1.1 先把题目读薄：那几条隐含前提才是关键

兔子繁殖这道题流传的版本很多，但核心设定基本一致：一开始有一对刚出生的兔子，兔子出生后需要经过一个月成熟，成熟之后每个月都能生出一对新的兔子，兔子永远不死。题目问的是第 n 个月总共有多少对兔子。这三条假设——一个月成熟、每月生一对、不死——看起来是废话，实际上每一条都在决定递推式的形状，改动其中任何一条，整个数列就会变样。

我见过有人把"一个月成熟"理解成"出生当月就能生"，那递推式就变成了 F(n) = 2 × F(n-1)，兔子数量每个月翻倍，第 20 个月就是五十多万对，跟题目原本想考的完全不是一回事。也有人把"每月生一对"记成"每月生两对"，那系数就变了。所以我个人的习惯是，动笔写代码之前先把这三条假设在心里默念一遍，写在注释里，后面不管谁来读代码，都能一眼确认模型没跑偏。

提示：面试或者做题时，如果题目描述比较简略，先跟对方确认"新生的兔子需要几个月才能生育"和"是否考虑死亡"，这两个问题的答案直接决定递推式的起始项和系数。

1.2 手推前几个月，递推关系自己会浮出来

我建议所有人在写代码之前都先在纸上推前几个月，这个动作花不了两分钟，但能省掉后面大量的调试时间。第一个月：只有一对刚出生的兔子，总数 1 对，这对兔子还没成熟。第二个月：这对兔子成熟了，但还是 1 对。第三个月：成熟的那对生了新的一对，现在有 1 对成熟的加 1 对刚出生的，总数 2 对。第四个月：成熟的那对继续生，第三个月出生的那对还没成熟，所以新生 1 对，总数 3 对。第五个月：第四个月时已经存在的 3 对里，有 2 对是成熟的（第二个月成熟的那对，加上第三个月出生、到第五个月刚好成熟的那对），所以新生 2 对，总数 5 对。

推到这里规律已经很清楚了：1、1、2、3、5、8、13、21……每一项等于前两项之和。这时候再回头看逻辑，为什么是前两项？因为第 n 个月的总数 = 上个月已有的兔子 + 这个月新生的兔子；而第 n 个月能生育的兔子，正好是第 n-2 个月就已经存在的所有兔子，因为第 n-1 个月才出生的那批到第 n 个月还不满一个月，不能生。这个推导链条是整道题的灵魂，把它想通了，递推式就是水到渠成的事，而不是硬记住一个公式。

1.3 起始项错位是最高频的低级错误

写代码时最常见的翻车点不是递推关系写错，而是起始项对不齐。标准写法是 F(1) = 1、F(2) = 1，但如果题目说的是"第一个月有一对成年兔子"，那第一个月就能生，结果会整体偏移一个月，正确答案应该对应标准斐波那契的 F(n+1)。这两种情况的数列看起来只差一项，实际输出会完全不同。

下面这张表把两种常见表述对齐一下，遇到具体题目时可以直接对照：