兔子繁殖这道题我在不同场合讲过不下二十遍从刚入行的新人到带过的实习生几乎每个人第一次手写递归都会栽在它上面。它表面上是道小学奥数式的应用题一对小兔子出生第二个月长成大兔子从第三个月起每个月生一对小兔子问第 n 个月一共有多少对兔子。但真正把它拆开来看里面藏着递归设计的三要素、递归树的重复计算问题、递推与记忆化的取舍、大数溢出的边界以及从 O(2^n) 一路优化到 O(log n) 的完整链路。可以说一道兔子繁殖把递归法该讲的东西全讲完了。这篇内容适合三类人看正在学递归但写不出终止条件的新手、能写出答案但说不清复杂度的人、以及面试前想把递推类题目一次性打通的人。我会从数学模型怎么来的讲起一路写到矩阵快速幂的落地代码中间穿插我自己踩过的坑和排查顺序代码给 Python、Java、C 三个版本你可以直接抄。1. 兔子繁殖问题的数学本质拆解1.1 从故事到递推式三个隐含假设决定了全部答案很多人拿到这道题第一反应是画图从第一个月画到第六个月画出 1、1、2、3、5、8然后恍然大悟哦是斐波那契。但我要说的是光记住数列没有意义你得知道这个数列是被什么假设逼出来的。原题里有三个关键约束缺一个结论就变样。第一个假设是成长周期固定为一个月。小兔子出生当月不算成熟第二个月才长成大兔子。第二个假设是成熟个体每月稳定产出一对不多不少且从成熟的那个月起就开始生。第三个假设是没有死亡、没有外部迁入迁出兔子只增不减且雌雄比例恒定为 1:1每对兔子贡献一对新兔。这三条摆在一起才构成了一个封闭的、确定性的、离散时间的人口增长模型。为什么强调这个推导过程因为实际工程里你遇到的递推问题边界条件往往就是被这类假设悄悄改掉的。比如把第二个月成熟改成第三个月成熟递推式立刻从 f(n)f(n-1)f(n-2) 变成 f(n)f(n-1)f(n-3)这就是经典的母牛生小牛问题。把每月生一对改成每月生两对系数就变成了 2。你如果只会背斐波那契题目稍微一改就废了。所以我在教别人的时候第一步永远不是写代码而是让他把每一条假设翻译成一个可以量化的条件写在纸上。这一步花五分钟后面能省两小时。1.2 递推关系是怎么推出来的按上个月留下来的加这个月新生的严谨一点的推导是这样的。设 f(n) 表示第 n 个月月末兔子对数的总和。第 n 个月的兔子可以分成两类一类是第 n-1 个月就已经存在的另一类是第 n 个月新出生的。第 n-1 个月已经存在的兔子到第 n 个月全部还在数量就是 f(n-1)这部分没有损耗。第 n 个月新出生的兔子只能由在第 n 个月已经成熟的母兔生产。而一只兔子要成熟必须在第 n-1 个月就已经存在并且它在第 n-1 个月时至少已经满两个月龄。换句话说第 n 个月能生育的兔子恰好就是第 n-2 个月月末就已经存在的全部兔子——因为第 n-2 个月存在的兔子到第 n 个月时年龄至少是两个月全部成熟了。所以新生数量等于 f(n-2)。两部分相加f(n) f(n-1) f(n-2)n ≥ 3。这个推导的关键点在于第 n 个月能生育的兔子 第 n-2 个月的总数这一步转换很多人卡在这里觉得应该是 f(n-1)。你可以这样想第 n-1 个月新出生的那批兔子到第 n 个月才一个月大还不能生所以不能算进生育群体剩下能生的正好是第 n-2 个月就存在的所有兔子。1.3 初始项到底取 f(1)1 还是 f(0)0这是第二个容易翻车的地方。初始条件取错整个数列就偏移了。标准兔子问题的设定是第 1 个月有一对新生的兔子第 2 个月它们长成大兔子但还没生所以前两个月都是 1。月份 n状态描述兔子对数 f(n)1一对小兔12一对大兔尚未生育13一对大兔 一对新生小兔24一对大兔 一对一月龄 一对新生35两对大兔 一对一月龄 一对新生56三对大兔 两对一月龄 两对新生8如果你在代码里把 f(0) 设成 0、f(1) 设成 1那得到的数列是 0,1,1,2,3,5,8数学上这叫标准斐波那契数列和兔子问题只差一个下标偏移。这两种写法都对但必须全局统一。我见过太多人前面用 f(1)1、f(2)1中间某处又写了个 f(0)0 去做循环起点结果算出来永远差一位调半天找不到原因。我的建议是写代码前先在注释里把前六项钉死运行完立刻对照。如果输出是 1,1,2,3,5,8 就对了如果出现 0,1,1,2,3 或者 1,2,3,5,8说明下标定义跑偏了回头改不要试图在后面的逻辑里打补丁。2. 朴素递归的第一版实现与它的真实代价2.1 最直白的递归写法三行代码对应三要素按递推式直接翻译成代码就是最朴素的递归版本。Python 版本如下def fib(n): if n 2: return 1 return fib(n - 1) fib(n - 2) print([fib(i) for i in range(1, 11)]) # 输出: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]这三行代码恰好对应递归的三要素我在带人时会把它们拆开讲清楚终止条件n 2时直接返回 1。这是递归的刹车没有它程序会无限往下调用直到栈溢出。注意这里用而不是是为了防御 n 传入 0 或负数的情况虽然兔子问题里 n 是正整数但写成更稳。递推关系fib(n-1) fib(n-2)。这一行是递归的发动机它把规模为 n 的问题降解成两个规模更小的同类子问题。这里必须保证子问题的规模严格小于原问题否则永远收敛不了。返回值语义函数返回的是第 n 个月的兔子对数。这一条最容易被忽略但它是所有错误的根源。如果你在某个分支里返回了别的东西比如返回了子问题的调用次数整个语义就乱了。Java 和 C 版本骨架完全一样只是要注意返回类型n 小的时候用int够n 超过 46 就得换long。我在第 4.2 节会专门讲溢出的边界在哪。2.2 调用树长什么样为什么 n40 就已经跑不动了朴素递归的问题不在结果而在过程。以 fib(5) 为例展开调用树你会发现fib(5) 调用 fib(4) 和 fib(3)fib(4) 调用 fib(3) 和 fib(2)fib(3) 被计算了两次fib(2) 被计算了三次到了 fib(40)fib(2) 会被重复计算上亿次。这不是夸张实测下来 Python 跑 fib(35) 大约需要 3 到 4 秒fib(40) 就要接近 40 秒。我做过一个粗略统计朴素递归的函数调用总次数大约是 2*f(n)-1而 f(40) 102334155也就是说光函数调用就是两亿次量级。时间复杂度写出来是 O(2^n)但这个上界其实偏松。精确一点的分析是递归树的每个节点产生两个子节点但两侧深度不同实际增长速率约等于黄金比例 φ ≈ 1.618 的 n 次方也就是 O(1.618^n)。1.618^40 大约是 2.28 亿和实测吻合。所以说 O(2^n) 是个安全但粗略的上界面试时你答 O(2^n) 没人扣分但能说出 1.618^n 会显得你真跑过。空间复杂度是 O(n)因为递归深度最大就是 n调用栈占用线性空间。这一点常被误认为也是指数级其实不是——栈是随调用深度增长的同一时刻栈上最多 n 层子调用返回后就弹栈了。2.3 递归深度不是主要矛盾重复计算才是初学者经常把两个问题搞混一个是递归太深会栈溢出另一个是递归太慢。在兔子繁殖这道题里n 通常不会超过几百递归深度完全不是问题Python 默认递归上限 1000 层跑 n500 都没事。真正要命的是重复计算。但如果你把这道题当成通用的递归训练就得知道深度的边界在哪。假设有人问第 5000 个月有多少对兔子Python 直接抛RecursionError: maximum recursion depth exceeded因为默认限制是 1000。这时候要么用sys.setrecursionlimit(10000)手动放宽要么干脆改用迭代。我个人的态度是能用迭代就别动递归上限改上限只是把崩溃点往后推真到了几万层物理栈内存照样撑不住而且崩的时候往往是段错误连堆栈信息都没有排查成本极高。顺带说一句Java 默认栈大小一般是 512KB 到 1MB每层栈帧几十字节大概也就撑个几千到一万层C 类似。所以递归深度超过一万基本都得换成显式栈或者迭代。2.4 递归三要素的自查清单写完递归函数我习惯按这个顺序过一遍基本上能拦住 90% 的 bug终止条件是否覆盖了所有最小规模的情况。兔子问题里最小规模是 n1 和 n2都要返回 1。如果只写了if n 1: return 1那 n2 时会继续往下调 fib(1) 和 fib(0)fib(0) 又进入不了终止分支直接无限递归。每次递归调用是否让问题规模单调减小。fib(n-1)和fib(n-2)都小于 n满足如果写成fib(n)就是死循环。返回值是否和函数语义一致。所有分支返回的必须是同一种东西不能一个分支返回数量、另一个分支返回布尔值。是否存在可以合并的重复分支。这是从能跑到跑得快的分水岭也是下一节要展开的内容。提示这三要素不是背下来的口诀而是排查工具。当你发现递归函数不返回或者返回错按这四条逐条对比盯着代码瞎看快得多。3. 三条优化路线的取舍与实现3.1 记忆化递归给重复计算装上缓存既然瓶颈是重复计算最直接的想法就是把算过的结果存起来。这叫记忆化Memoization属于自顶向下的优化代码改动极小from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return 1 return fib(n - 1) fib(n - 2) print(fib(100)) # 输出: 354224848179261915075lru_cache这一行装饰器干的事就是函数被调用时先查缓存命中直接返回没命中才真正执行执行完把结果写进缓存。加上它之后每个 n 只会被真正计算一次时间复杂度从 O(1.618^n) 直接降到 O(n)空间复杂度 O(n) 用于存缓存。如果你在面试或者不允许用装饰器的环境手写一个字典版本更清楚def fib(n, memoNone): if memo is None: memo {} if n 2: return 1 if n in memo: return memo[n] memo[n] fib(n - 1, memo) fib(n - 2, memo) return memo[n]这里有个新手常踩的坑把 memo 定义成默认参数def fib(n, memo{})。Python 的默认参数只在函数定义时求值一次所有调用共享同一个字典看起来能用实际上多次调用之间会串数据。虽然对斐波那契这种纯函数不影响结果但这是坏习惯一旦换成有副作用的问题就会出诡异 bug。正确做法就是上面那样默认给 None函数内部再初始化。记忆化递归的优点是保留了递归的思维直观性你不用担心计算顺序想到哪算到哪缺点是仍然有 O(n) 的栈开销n 特别大时会栈溢出。所以它适合递推式复杂、顺序不好确定的场景比如树形 DP、博弈类问题。对兔子繁殖这种线性递推其实有点杀鸡用牛刀。3.2 迭代递推两个变量就能搞定的空间优化既然 f(n) 只依赖前两项那根本不需要存整个数组也不需要递归栈两个滚动变量就够def fib(n): if n 2: return 1 a, b 1, 1 # a 代表 f(n-2)b 代表 f(n-1) for _ in range(3, n 1): a, b b, a b # 先算新的 b同时旧的 b 挪给 a return b这段代码的时间复杂度 O(n)空间复杂度 O(1)是实际工程里最推荐的写法。我特别喜欢拿它当例子讲滚动变量这个技巧因为它把只需要保留有限个历史状态这件事表现得极其干净。a, b b, a b这一行是 Python 的元组解包右边的b和ab会先全部算完再赋值所以不用担心覆盖问题。换成 Java 或 C 就得老老实实用临时变量public static long fib(int n) { if (n 2) return 1L; long a 1, b 1, tmp; for (int i 3; i n; i) { tmp a b; a b; b tmp; } return b; }C 版本结构一致只是把long换成long longlong long fib(int n) { if (n 2) return 1; long long a 1, b 1, tmp; for (int i 3; i n; i) { tmp a b; a b; b tmp; } return b; }迭代版的另一个好处是天然支持取模。如果要算 f(10^9) 对 10^97 取模的结果递归版根本开不了那么大的栈迭代版只要循环 10 亿次就行——虽然慢但至少不崩。当然 10 亿次循环也不现实这就轮到下一节的矩阵快速幂出场了。3.3 矩阵快速幂把 O(n) 压到 O(log n)兔子繁殖的递推式是线性的、常系数的这类递推都可以用矩阵乘法表达。核心恒等式是[ f(n) ] [ 1 1 ] ^ (n-2) [ f(2) ] [ f(n-1) ] [ 1 0 ] * [ f(1) ]更常见的写法是用[[1,1],[1,0]]的 k 次幂其左上角元素就是 f(k1)。推导过程不复杂设转移矩阵 M [[1,1],[1,0]]那么 [f(n), f(n-1)]^T M * [f(n-1), f(n-2)]^T反复代入 n-2 次就得到上面的式子。关键在于矩阵的幂可以用快速幂来做M^k 可以拆成 M^(k/2) 的平方偶数情况一路折半奇数情况多乘一次 M总共只需要 O(log k) 次矩阵乘法。每次 2x2 矩阵乘法是常数时间所以整体复杂度 O(log n)。MOD 1_000_000_007 def mat_mul(A, B): return [ [(A[0][0]*B[0][0] A[0][1]*B[1][0]) % MOD, (A[0][0]*B[0][1] A[0][1]*B[1][1]) % MOD], [(A[1][0]*B[0][0] A[1][1]*B[1][0]) % MOD, (A[1][0]*B[0][1] A[1][1]*B[1][1]) % MOD] ] def mat_pow(M, e): R [[1, 0], [0, 1]] # 单位矩阵快速幂的累乘器 while e: if e 1: R mat_mul(R, M) M mat_mul(M, M) e 1 return R def fib(n): if n 2: return 1 M mat_pow([[1, 1], [1, 0]], n - 2) return (M[0][0] M[0][1]) % MOD验证一下n5 时M^(3) [[3,2],[2,1]]左上角加右上角 32 5正确。Java 版本要特别注意乘法溢出因为两个小于 MOD 的数相乘接近 10^18刚好在 long 的安全范围内long 上限约 9.22×10^18但如果是三次累加就会溢出所以每次加法后立刻取模static final long MOD 1_000_000_007L; static long[][] mul(long[][] a, long[][] b) { long[][] c new long[2][2]; for (int i 0; i 2; i) { for (int j 0; j 2; j) { for (int k 0; k 2; k) { c[i][j] (c[i][j] a[i][k] * b[k][j]) % MOD; } } } return c; } static long fib(long n) { if (n 2) return 1L; long[][] res {{1, 0}, {0, 1}}; long[][] base {{1, 1}, {1, 0}}; long e n - 2; while (e 0) { if ((e 1) 1) res mul(res, base); base mul(base, base); e 1; } return (res[0][0] res[0][1]) % MOD; }用这个写法跑 n10^18耗时基本在微秒级肉眼感觉不到。这已经不是优化了是换了套算法。3.4 四种方案横向对比到底该选哪个方案时间复杂度空间复杂度适用场景主要风险朴素递归O(1.618^n)O(n) 栈教学演示、验证递推式n35 就卡死记忆化递归O(n)O(n) 缓存 O(n) 栈递推式复杂、顺序难定n 大时栈溢出迭代递推O(n)O(1)绝大多数实际场景n 极大时循环太慢矩阵快速幂O(log n)O(1)n 达到 10^9 以上实现易错、需取模我的选择习惯是面试写迭代笔试看数据范围工程里看是否有大数需求。如果 n ≤ 10^6迭代最稳代码短、无坑、好调试。如果 n 到 10^9 甚至 10^18那就只能上矩阵快速幂同时必须配取模。记忆化递归我一般只在讲课时用因为它最好地展示了优化这个动作本身。4. 落地实操从写代码到验证通过的完整流程4.1 开写之前先把测试用例钉死前面说了要钉死前六项这里给一套完整的手工计算表你在本地跑代码时直接拿来对输入 n期望输出 f(n)说明11边界只有初始的一对21边界还没生育32第一次生育43—55—1055常见校验点206765中等规模5012586269025超过 int 范围把这几个点写成断言是防止改动引入回归的最省事办法cases {1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 10: 55, 20: 6765, 50: 12586269025} for n, expect in cases.items(): got fib(n) assert got expect, fn{n} 期望 {expect} 实际 {got} print(全部通过)跑出全部通过这四个字心里才踏实。这套用例我从学这道题开始一直用到现在前后改了十几年没换过。4.2 溢出边界n 到多少就不再安全这是兔子繁殖题里最容易被忽略、也最容易在线上翻车的地方。不同语言、不同整数类型的承载上限完全不一样类型最大值对应的最大 nint32 位有符号2,147,483,647n 46f(46)1836311903long long64 位有符号9,223,372,036,854,775,807n 92Python int无上限任意具体的临界点f(46) 1836311903f(47) 2971215073已经超过 int 上限。f(92) 7540113804746346429还在 long 范围内f(93) 12200160415121876738超过 2^63-1直接溢出成负数。所以如果你用 Java 的long算 f(93)会得到一个负数这不是 bug是溢出。处理办法有三种看场景选只关心结果对某个数取模最省事全程取模永远不会溢出矩阵快速幂就属于这一类。需要精确大数Python 天然支持Java 用BigIntegerC 得自己写高精度或者用第三方库。只关心数量级用浮点和 Binet 通项公式估算但要注意精度问题n 大了浮点会失准。Binet 公式是另一个有趣的东西f(n) (φ^n - ψ^n) / √5其中 φ (1√5)/2ψ (1-√5)/2。这个公式理论上 O(1)但实际用不了——n70 左右双精度浮点就开始丢精度算出来的整数部分是错的。我试过用 Python 的 Decimal 提高精度能撑到 n200 左右再往上还是不行而且速度还不如迭代。所以它只适合做理论分析或者粗略估算别拿它写生产代码。4.3 取模运算的坑负数、时机、和多处取模取模看起来简单实际上有几个细节容易出问题。第一个是负数取模。在 Python 里-1 % 7等于 6符合数学定义但在 Java 和 C 里-1 % 7等于 -1是截断取余。如果你的中间结果可能为负比如写了a - b这种减法Java 那边必须写成((a - b) % MOD MOD) % MOD才能保证结果非负。兔子繁殖本身是纯加法一般不会出这个问题但换成组合数、卡特兰数之类的题目就会踩。第二个是取模的时机。原则是能早取就早取因为加法乘法的取模满足分配律(a%m b%m) % m (ab) % m。你在每次加法后立刻取模中间值就永远不会超过 2m自然不会溢出。反过来如果攒到最后再取中间可能早就溢出了取模也救不回来。第三个是多矩阵连乘时每一层都要取模。矩阵快速幂里一次乘法涉及 8 次乘加每加一个乘积就取一次模最稳。我在 3.3 节的 Java 代码里就是这么写的c[i][j] (c[i][j] a[i][k] * b[k][j]) % MOD虽然多几次取模运算但换来的是绝对安全。注意a[i][k] * b[k][j]这一步在 long 下是安全的因为两个数都小于 10^97乘积小于 10^18未超 long 上限。但如果你的模数是 10^18 级别这一步就会溢出必须用__int128或者乘法转加法的技巧。选模数时心里要有一根弦。4.4 对拍验证手算靠不住的时候怎么办当你把三种实现朴素递归、迭代、矩阵快速幂都写完了最有效的验证方式是互相对拍小范围内三个结果必须完全一致。for n in range(1, 31): a fib_recursive(n) # 朴素递归n小的时候跑得动 b fib_iter(n) # 迭代 c fib_matrix(n) # 矩阵快速幂小 n 时不取模或模数足够大 assert a b c, fn{n}: {a} {b} {c} print(三种实现结果一致)对拍的价值在于你不需要知道正确答案是什么只要三种独立实现的思路都指向同一个值那大概率就是对的。这是我在刷题和做工程时最依赖的验证手段。手算容易错一位三种代码同时错成一样的概率极低——除非你的下标定义从一开始就是三份一起抄错的所以还是要配合 4.1 节的定点用例一起用。另外一个小技巧把 n 从 1 到 30 的结果整串打印出来肉眼扫一眼有没有出现负数溢出信号、有没有突然变大跳变下标错位信号很多问题一眼就能看出来。5. 常见问题排查与同类题型延伸5.1 报错速查表这些坑我基本都踩过现象大概率原因排查动作结果差一位永远少一个初始项定义不统一打印前六项对照 1,1,2,3,5,8n40 以上卡住不动用了朴素递归换迭代或加缓存抛出 RecursionError递归深度超默认上限改迭代或谨慎调高上限输出负数long / int 溢出换大数类型或全程取模矩阵版结果和迭代对不上幂次算成 n 而不是 n-2检查指数与单位矩阵取模后全部为 0模数取得太小或写错常量检查 MOD 常量定义这张表我建议你保存下来遇到问题先对号入座比从零开始读代码快得多。特别是第一行差一位和第四行负数在同类递推题里的出现频率高得离谱。5.2 递归写不出来的排查顺序如果让你现场手写递归卡壳了按这个顺序过先问自己最小的、不需要再分解的情况是什么把终止条件写死。兔子问题里就是 n1 和 n2。再问规模为 n 的答案能不能用规模更小的答案拼出来能拼出来就把表达式写出来这就是递推关系。检查返回值类型是否统一所有分支必须返回同一语义的东西。最后才考虑性能先让它跑对再让它跑快。这个顺序千万不能颠倒。我见过太多人一开始就纠结会不会太慢结果连递推式都没写对优化了个寂寞。先正确再高效这句话在递归题上是铁律。另一个常见心理障碍是想不清楚递归怎么展开。我的建议是不要在脑子里展开人类大脑最多能同时跟踪三层调用再深就乱了。你就相信数学归纳法假设 f(n-1) 和 f(n-2) 都能返回正确结果那么 f(n) 的表达式也一定是对的。这种信任子问题的心态是写好递归的前提。5.3 一类题的通用套路换个故事还是同一个递推兔子繁殖之所以经典是因为它是最小可用的递推载体。把它稍微变形就是面试里的常客跳台阶问题每次可以跳 1 级或 2 级问跳到第 n 级有多少种跳法。答案就是 f(n)f(n-1)f(n-2)和兔子繁殖一模一样只是故事换了。理解成最后一步是跳 1 级还是 2 级递推式立刻出来。母牛生小牛每头母牛从第 4 年开始每年生一头小母牛问第 n 年有多少头。递推式变成 f(n)f(n-1)f(n-3)因为能生的只有 3 年前就存在的那些。这就是改变成熟周期参数的直接结果。骨牌铺方格用 1×2 的骨牌铺满 2×n 的方格问方案数。同样是 f(n)f(n-1)f(n-2)——最右边要么竖放一块要么横放两块。打家劫舍类问题不能偷相邻的两家问最大收益。递推式是 f(n)max(f(n-1), f(n-2)a[n])结构一样只是加法换成了取最大值。我的经验是这类题的通用解法分三步定义状态、写递推式、定边界。状态定义决定了一切比如f(n) 表示第 n 个月的总对数这种定义是自洽的如果你定义成第 n 个月新生的对数递推式就得重写。定义清楚之后递推式往往是自然的边界条件只需要手工算前几项。最后分享一个我自己用了很多年的小习惯每写完一个递推解我都会用三个不同的 n 值手算一遍通常是 n1、n2、n3 加上一个中等值比如 n6。手算三次花不了两分钟但能拦住绝大多数边界错误。这个习惯是从一次线上事故里养成的——当时一个统计模块的初始项写成了 0 和 1导致所有结果整体偏移一位测试用例恰好都是大数谁也没发现上线三天后才被业务方指出来。从那以后我就认准一个理递推题的正确性靠的不是聪明靠的是把边界一个一个钉死。