最近有个做后端的朋友把一段代码发过来说程序跑了两分钟还没出结果问我是不是电脑该换了。我扫了一眼就是一个求第 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(n1)。这两种情况的数列看起来只差一项实际输出会完全不同。下面这张表把两种常见表述对齐一下遇到具体题目时可以直接对照