我第一次用递归写斐波那契是在学函数式编程概念的时候。老师给了一段三行代码逻辑清爽像数学定义直接翻译过来。当时我真觉得递归就是世界上最优雅的写法。直到某天我把参数从 10 调到 40笔记本风扇开始咆哮光标转了几秒才吐出一个结果才意识到教科书里的“简洁”和真实运行时的“性能”差了十万八千里。Python 里用递归函数实现斐波那契数列这个话题值得好好拆开正确的边界定义、底层的调用机制、指数级的重复计算、三种常见的优化手段以及最后怎么根据业务场景选型。这篇就按我实际中用到的顺序把思路和坑一起讲清楚。1. 先把斐波那契数列的“递推基因”看清楚1.1 定义边界比背公式更重要斐波那契数列在不同地方有不同起点常见两种一种是 F(0)0、F(1)1另一种是 F(1)1、F(2)1。很多博客起步省略 F(0)代码里从 F(1) 和 F(2) 开始。这个差别不大但踩过坑的人都知道下标的偏移能让你 debug 到怀疑人生。比如“求第 5 项”按第一种定义是 3按第二种定义是 5。我的建议是代码里统一用 F(0)0、F(1)1。这么写有两个好处第一n 和 Python 列表下标对齐f(n) 直接对应索引 n第二后续做记忆化或查表时边界条件简单不用额外处理前两项之外的偏移。别小看这个约定你在爬楼梯、铺砖问题里复用斐波那契逻辑时下标统一能省很多事。1.2 递归式与通项公式的关系数列的核心是递推关系 F(n)F(n-1)F(n-2)。从数学上看这是一个二阶线性齐次递推特征方程是 x²x1两个根分别约等于 1.618 和 -0.618。解出通项公式后F(n) 可以写成黄金比例的幂次形式也就是所谓的比奈公式。比奈公式看起来很厉害但在 Python 里直接拿 float 去算并不靠谱。n 稍微大一点浮点数精度就不足以表示准确的整数结果。哪怕你用了高精度浮点库逻辑上也绕了一圈。这恰恰说明真正可落地的斐波那契计算还是应该走整数运算路线递推、递归加缓存、矩阵快速幂等。通项公式的用处更多是估算数量级比如判断 F(1000) 大概有多少位这个用对数算一算就好。1.3 为什么递归是“最像数学归纳法”的写法递推关系本身就带着递归的味道你想计算 F(n)就得先计算 F(n-1) 和 F(n-2)然后它们再去依赖各自的子项直到撞上边界 F(0)0、F(1)1。这个结构可以用一个生活类比来理解一排人按规则传递数字第 n 位需要问第 n-1 位和第 n-2 位要结果最后排头的两个人手里是基准数字。你从第 n 位开始反向往下问就是一个标准的递归过程。所以初学者看到斐波那契会自然写出递归不是偶然。它是最符合人类归纳直觉的表达方式。问题就在于这个“往下问”的过程中很多人会问同一个编号的人很多次导致计算量爆炸。下一节我们来看这个爆炸到底有多严重。2. 教科书版的递归一眼看懂但别急着上线2.1 线上跑一遍风扇告诉你真相先给出最基础的递归实现def fib_recursive(n: int) - int: if n 0: return 0 if n 1: return 1 return fib_recursive(n - 1) fib_recursive(n - 2)逻辑没错但你把 n 分别设成 10、20、30、40 去跑会发现耗时呈指数上升。n10 和 20 都是毫秒级n30 开始能感觉到卡顿n40 通常要等好几秒甚至更久。这不是 Python 太慢也不是电脑太差而是算法本身的调用次数在指数增长。2.2 重复计算到底有多严重调用树与调用次数我们可以把调用过程画成一棵树。以 n5 为例fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ │ ├── fib(1) │ │ │ └── fib(0) │ │ └── fib(1) │ └── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(3) ├── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(1)注意fib(3) 被调用了两次fib(2) 被调用了三次。随着 n 增大这种重复不是成比例增长而是成指数增长。设 C(n) 为计算 fib(n) 的总调用次数边界 C(0)C(1)1递推式 C(n)C(n-1)C(n-2)1。解出来会发现 C(n)2F(n1)-1。不要小看这个公式。F(41) 大约是 165580141所以 n40 时的总调用次数约 3.3 亿次。我用几个常见数值列了一下n调用次数约值肉眼感受10177瞬间2021891瞬间302692537轻微卡顿3529860703明显等待40331160281足够你去喝口水3.3 亿次 Python 函数调用每次都要压栈、传参、返回值这个开销在普通开发机上往往要数秒甚至几十秒。n50 时调用次数达到数百亿级别基本就别想跑完了。2.3 Python 递归函数调用的隐性开销有人可能会说递归调用虽然次数多但每次很轻啊。放到 C/C 里可能确实如此但 Python 是解释型动态语言函数调用本身就是相对昂贵的操作。每次递归都要创建一个新的栈帧保存局部变量和调用位置解释器还要做类型检查与引用计数这些成本叠加起来让同样的递归算法在 Python 里跑得比静态编译型语言慢得多。即便我们不考虑解释器开销纯递归还有一个限制调用深度。Python 默认递归深度上限通常是 1000所以计算 fib(1000) 会直接抛 RecursionError。这个问题不是加了缓存就能解决的因为哪怕每个 n 只算一次深度还是要一层层往下走到 0。要改变“递归很直观但代价不小”的现状必须从算法改造和工程选型两个方向同时入手。3. 让递归“能打”的三个改造方向3.1 记忆化把重复计算的账本记下来最简单的优化思路是把已经算过的 Fibonacci(n) 结果存起来。下次再有人问同样的 n直接从字典里查而不是重新展开整棵调用树。手写记忆化版本如下def fib_memo(n: int, cache: dict | None None) - int: if cache is None: cache {} if n in cache: return cache[n] if n 2: return n result fib_memo(n - 1, cache) fib_memo(n - 2, cache) cache[n] result return result重点在于不要用可变对象作为函数参数的默认值。如果写成def fib_memo(n, cache{})那么这个字典在函数定义时只创建一次所有调用共享它。单线程里一般能跑但如果你在同一个进程里用两种不同规则的递归或者并发调用数据就可能被污染。用None作为默认值在函数内部按需创建是更安全的方式。记忆化把时间复杂度从指数级别降到 O(n)。因为对于每个 n我们只真正计算一次后面的调用全部命中缓存。我实测 fib_memo(500) 瞬间返回而纯递归在 n50 就已经歇菜。这个改进在原理上完全复制了“用空间换时间”的思想。3.2 functools.lru_cache官方免费的记忆化装饰器手写缓存能加深理解生产代码里我更推荐直接用标准库的functools.lru_cachefrom functools import lru_cache lru_cache(maxsizeNone) def fib_lru(n: int) - int: if n 2: return n return fib_lru(n - 1) fib_lru(n - 2)lru_cache会按照函数参数自动缓存返回值。maxsizeNone表示不限制缓存条目数对于普通斐波那契需求完全够用。如果 n 的取值空间非常大又想控制内存可以设置一个合理的大小比如maxsize128但这样在反复进行范围穿插的调用时可能会把旧结果挤出缓存性能反而不稳定。额外提醒两点。第一lru_cache不仅缓存了结果还能通过fib_lru.cache_info()查看命中率这是定位性能瓶颈的好工具。第二装饰器缓存的是“参数组合”如果函数有其他非哈希参数lru_cache 会用不了。对于只有单个整数参数的斐波那契函数完全没问题。3.3 尾递归与 Python 的现实别硬来另一个常见的优化方向是改写成尾递归形式def fib_tail(n: int, a: int 0, b: int 1) - int: if n 0: return a return fib_tail(n - 1, b, a b)递归调用的结果直接返回不再参与额外计算这在理论上可以复用栈帧把递归深度保持在常量也就是所谓的“尾调用优化”。但 Python 标准解释器CPython并没有实现这个优化。所以你在 Python 里写尾递归该压栈还是压栈n1000 依然会栈溢出。这里千万不要觉得“改成尾递归就安全了”。这不是说尾递归公式没有价值。它提供了一个很好的思路把中间结果a、b作为显式参数传递本质上就是在手动模拟循环累加。你可以顺势把它变成真正的迭代代码这才是 Python 里尾递归的正确归宿。3.4 sys.setrecursionlimit 能解决一切吗有人遇到 RecursionError 后的第一反应是调大递归深度限制import sys sys.setrecursionlimit(10000)这么做在某些时候能让你从 n1000 算到 n9000但并不是万无一失。CPython 的递归栈最终是压在 C 语言的调用栈上操作系统对线程栈的大小有硬限制。当你把递归深度调到十万、百万级别时进程可能直接段错误Segmentation Fault崩溃连 Python 异常都不会抛。这种崩溃很难排查因为不是代码逻辑错而是运行时环境撑不住了。所以 my 的经验是setrecursionlimit 最多用来给中小规模的递归留点余量比如默认 1000 太紧调到 5000 还能接受但如果你发现自己需要把限制调到几万甚至更高那说明这个算法本身不适合用递归实现在 Python 里应该立刻切换成迭代或显式栈方案。4. 递归、迭代、矩阵快速幂谁才是真正的生产选手4.1 迭代法最简单且实用的版本如果你的目标只是“求第 n 个斐波那契数”我最推荐的是从一个不起眼的迭代版本开始def fib_iterative(n: int) - int: a, b 0, 1 for _ in range(n): a, b b, a b return a这个函数时间复杂度 O(n)空间复杂度 O(1)。它没有递归没有缓存不用担心栈溢出代码量也短。更重要的是Python 的循环执行速度远高于函数递归调用。实测之下算 fib(10000) 迭代版也是一眨眼的工夫。有人可能觉得迭代版“不够数学”但它恰恰是把斐波那契的递推本质用最直接的方式表达出来了每一步让 a 前进为 b让 b 前进为 ab。如果你需要同时打印前 n 项迭代也一样方便每轮循环把 a 输出即可。4.2 矩阵快速幂理论上的 O(log n)但别忽略大数成本斐波那契与矩阵有深刻的联系。如果定义矩阵 M [[1, 1], [1, 0]]那么 M 的 n 次幂的右上角元素正好是 F(n)。于是问题变成快速计算矩阵幂标准写法如下def mat_mul(a, b): return [ [a[0][0] * b[0][0] a[0][1] * b[1][0], a[0][0] * b[0][1] a[0][1] * b[1][1]], [a[1][0] * b[0][0] a[1][1] * b[1][0], a[1][0] * b[0][1] a[1][1] * b[1][1]] ] def fib_matrix(n: int) - int: if n 0: return 0 base [[1, 1], [1, 0]] result [[1, 0], [0, 1]] while n 0: if n 1: result mat_mul(result, base) base mat_mul(base, base) n 1 return result[0][1]矩阵快速幂理论上的时间复杂度是 O(log n)看起来比迭代的 O(n) 高级很多。但这里有个工程上很容易忽略的事实斐波那契数的大小是随着 n 指数增长的F(n) 的十进制位数约为 0.209 倍 n 加常数也就是说 n1000 时 F(1000) 已经有 209 位左右。Python 的大整数虽然不会溢出但位数越长加法和乘法的耗时就越高。矩阵乘法里不只是加法还有大整数乘法它的成本比加法高不少。因此在 n 比较小几百、几千时矩阵快速幂通常跑不过简单迭代只有当 n 大到让 O(log n) 的乘法次数优势盖过单次大整数乘法的开销时它才有胜出的可能。但 n 特别大时结果本身的数字就超长光存储和输出都是问题。所以矩阵快速幂更像是一个让人敬畏的数学玩具日常业务很少真正需要它。4.3 复杂度对比表这里把几种方案放一张表里方便横向对比方案时间复杂度空间复杂度是否能爆栈适用场景纯递归O(2^n)O(n)是教学演示、理解递归记忆化递归O(n)O(n)是同时需要递归思想和小规模计算lru_cacheO(n)O(n)是对多个 n 反复取值的场景迭代O(n)O(1)否生产环境的最优解矩阵快速幂O(log n)O(log n)否理论复杂度表演、特定超大 n 场景注意“记忆化递归和迭代都是 O(n)”为什么实际跑起来迭代往往更快因为递归即使有缓存也要一层层调用和返回函数调用的固定开销比循环大。迭代还省去了缓存字典的读写所以日常我几乎总是选迭代。4.4 选型建议我的个人原则可以归纳成一句话递归用来思考迭代用来执行。如果你想给学生讲清楚“递推关系怎么翻译成代码”那就用纯递归如果你想自己快速算一个不超过几千的数直接上迭代如果你要在同一个程序里反复查询很多不同的 n那lru_cache记忆化递归会更方便因为每次查询如果命中缓存就是 O(1)如果 n 到了天文数字级别又非要算精确值那矩阵快速幂才有那么点表演价值。实际项目中我大概有一半以上的场景是直接在迭代和查表之间选。5. 别让递归把你框死Python 生态下的几个进阶玩法5.1 用生成器做无限斐波那契递归和迭代都是为了求第 n 项或前 n 项。但如果想持续地消费斐波那契数列比如每生成一个就处理一个生成器是更优雅的选择def fib_generator(): a, b 0, 1 while True: yield a a, b b, a b配合itertools.islice可以轻松取前 20 项from itertools import islice for value in islice(fib_generator(), 20): print(value)这种惰性求值的好处是你不需要把整个序列存内存。递归、矩阵、迭代都解决不了“无限”的问题生成器天生就是为流式拆的。而且它和迭代的递推公式完全一致只是把每次循环的a用yield送了出去写起来也不难。5.2 递归深度限制的本质和工程规避前面提到过递归深度限制这里再往深挖一层。sys.getrecursionlimit()返回当前递归深度限制默认是 1000。这个数字不是随便定的它既要给 Python 解释器本身的调用留空间也要防止 C 栈溢出。一旦你决定用递归就要心里有数n500 以内基本安全n5000 可能需要调高限制且取决于平台n50000 就不要想用递归了趁早转显式栈。显式栈的思路是用一个 Python 列表模拟递归调用栈每次把“需要计算的子问题”压栈循环处理。天然绕过了调用深度限制因为栈不占用 C 调用栈。但斐波那契这样简单的例子用显式栈反而绕远不如直接迭代。5.3 伪装成斐波那契的实际问题很多常见问题表面上看和斐波那契没半点关系转化后它的递推式一模一样。比如爬楼梯每次可以走 1 级或 2 级问走到第 n 级有多少种不同走法。设 f(n) 为走到第 n 级的方法数第一步走 1 级则剩余 f(n-1)第一步走 2 级则剩余 f(n-2)所以 f(n)f(n-1)f(n-2)。边界 f(1)1、f(2)2本质上就是斐波那契的平移。这类问题最常见的坑是“少走一步”当你把爬楼梯实现成递归后测试 n5、n10 都没问题n50 就开始超时然后才想起来这是斐波那契。所以遇到递推题第一反应应该先画出递推式再决定用递归还是迭代而不是看到“每一步有两种选择”就无脑递归。6. 调试递归函数的实战经验打印、计时与并发6.1 用带缩进的打印还原调用树递归函数出错时最难的不是看逻辑而是看调用过程到底发生了什么。我经常在一开始加一个depth参数把每次调用打印出来def fib_debug(n: int, depth: int 0) - int: print( * depth ffib({n}) called) if n 2: return n return fib_debug(n - 1, depth 1) fib_debug(n - 2, depth 1)n 取 5 左右屏幕上会出现一棵缩进的树。你会发现同一个 fib(3) 出现在不同层级里这就是重复计算的实锤。不过要提醒一句千万别拿这个 debug 版去跑 n40输出长度够你翻几屏。调试完就换回正常版本。6.2 统计调用次数闭包或装饰器想验证“调用次数是不是 2F(n1)-1”可以写一个简单的装饰器统计总调用次数def call_counter(func): def wrapper(n, *args, **kwargs): wrapper.calls 1 return func(n, *args, **kwargs) wrapper.calls 0 return wrapper call_counter def fib(n): if n 2: return n return fib(n - 1) fib(n - 2)跑完fib(30)后访问fib.calls就能看到精确的数字。但注意如果你在这个装饰器外面又套了lru_cache统计到的就不是原始调用次数而是“实际真正执行函数体的次数”因为命中了缓存的调用在装饰器那一层就返回了。不同统计口径会得出不同结论使用前一定要想清楚自己要看什么。6.3 计时基准测试的几个坑我一开始对比递归和 lru_cache 时犯过一个低级错误先调了fib_lru(1000)再拿fib_lru(500)做基准测试结果第二个调用飞快因为缓存里早就存了前面的结果。这不是算法快而是缓存命中。如果要公平对比应确保每个方案都是干净的起点。对于 lru_cache可以在计时前调用fib_lru.cache_clear()或者干脆把基准测试放到新启动的 Python 进程里。另外Python 垃圾回收器如果在递归计算中途跑起来会让计时结果多出不少噪声。做相对比较时可以在测试代码里加一行gc.disable()测完再还原。别小看这些细节没有统一控制变量结论很容易失真。6.4 递归里的共享状态与线程安全如果要用递归加缓存处理并发任务就要注意缓存字典的线程安全问题。虽然 CPython 有 GIL单个字典的读写大部分情况下不会被拆成两个字节码但你的函数体可能是先查缓存再递归再写缓存中间穿插了多次 GIL 切换。两个线程同时计算同一个 n就可能出现重复计算极端情况下还会把不完整的值写入缓存。简单粗暴的解决办法是加锁但加锁后递归会退化得更慢不划算。更工程化的做法是进程启动时直接用迭代把需要范围内的斐波那契算好放进预生成的大数组后续所有线程只做 O(1) 查表。没有递归、没有共享可变缓存、没有锁性能最好也最安全。说到底递归适合表达逻辑但到并发环节越简单的数据结构越让人省心。我现在的习惯是看到任何“递归实现某数列”的题目先在心里过三个问题——递归深度有多少重复计算有多少改成迭代要多长时间斐波那契是递归入门题但正因为太简单很多人只背下了三行代码忽略了它背后展示的算法代价。如果你想快速求值迭代循环毫秒级完事如果你想理解分治和记忆化那就好好研究递归调用树和缓存穿透。上面这些坑我基本都踩过希望你少走几步。