使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
当你用Python写一个函数来递归地计算斐波那契数列时，你会发现它的速度慢得惊人，尤其是在你需要计算较大的斐波那契数时。这可不是巧合，背后藏着一些深刻的原因，我们来好好掰扯掰扯。
想象一下，你想计算 `fib(5)`。按照递归的定义，`fib(5)` 等于 `fib(4)` 加上 `fib(3)`。
`fib(4)` 又等于 `fib(3)` 加上 `fib(2)`。
`fib(3)` 又等于 `fib(2)` 加上 `fib(1)`。
你看到的这个过程，其实在电脑里执行的时候，会创建一个“调用栈”（call stack）。每次函数被调用，都会在栈顶压入一个新的“帧”（frame），记录下这个调用的上下文信息（比如局部变量、返回地址等等）。当函数执行完毕，它的帧就会从栈顶弹出。
现在，我们来可视化一下 `fib(5)` 的计算过程：
```
fib(5)
fib(4)
fib(3)
fib(2)
fib(1) > 返回 1
fib(0) > 返回 0
fib(1) > 返回 1
fib(2)
fib(1) > 返回 1
fib(0) > 返回 0
fib(3)
fib(2)
fib(1) > 返回 1
fib(0) > 返回 0
fib(1) > 返回 1
```
仔细看看上面这个展开图，有没有发现什么不对劲？
罪魁祸首一：重复计算 (Redundant Computations)
重点来了！请注意 `fib(3)` 这个部分。在计算 `fib(5)` 的过程中，`fib(3)` 被计算了 两次。一次是在计算 `fib(4)` 的时候，另一次是直接作为 `fib(5)` 的一部分。
更糟糕的是，`fib(2)` 被计算了 三次。`fib(1)` 和 `fib(0)` 就更不用说了，它们被计算的次数多到你数不过来！
想想看，当你计算 `fib(10)` 时，`fib(9)` 和 `fib(8)` 各算一次。但 `fib(9)` 又要算 `fib(8)` 和 `fib(7)`，而 `fib(8)` 又要算 `fib(7)` 和 `fib(6)`。这样一来，`fib(7)`、`fib(6)` 等等，很多中间结果都会被反复计算。
这种重复计算的模式，随着 `n` 的增大，爆炸式增长。斐波那契数列的递归实现，其时间复杂度大约是 O(2^n)，这个增长速度比指数还快。你可以把它想象成一棵二叉树，每一层都在分裂，而我们实际上只需要树叶上的值。
罪魁祸首二：函数调用的开销 (Function Call Overhead)
在 Python 里，每一次函数调用都会带来一些额外的开销。你需要创建栈帧、保存局部变量、进行参数传递、执行函数体，最后返回结果。即使是最简单的函数调用，这些步骤也需要时间。
在递归调用中，这些开销被重复地叠加。每次 `fib(n)` 调用 `fib(n1)` 和 `fib(n2)`，都意味着两次新的函数调用。当 `n` 变大，这个调用链就会变得非常长，累积的函数调用开销就成了一个显著的瓶颈。
举个例子，你就明白了：
假设我们要计算 `fib(30)`。
朴素递归： 会进行数十万甚至数百万次的函数调用，而且其中大量的计算是完全重复的。程序会卡很久。
改进方法（后面会讲）： 比如使用迭代或者记忆化（memoization），计算 `fib(30)` 几乎是瞬时的。
为什么不直接用迭代？
理解了递归的慢，你可能就想：“为什么不直接用循环来计算呢？” 没错，用循环迭代地计算斐波那契数列，只需要保持前两个数，然后不断更新，非常高效。时间复杂度是 O(n)，空间复杂度是 O(1)。
```python
def fib_iterative(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(n 1):
a, b = b, a + b
return b
```
这个版本的 `fib_iterative(30)` 会瞬间完成。
如何“拯救”递归？—— 记忆化 (Memoization)
虽然朴素的递归慢，但我们可以通过一种叫做“记忆化”的技术来挽救它。记忆化的核心思想是：如果一个子问题的解已经被计算过，就直接返回结果，而不是重新计算。
在斐波那契数列的例子中，我们可以用一个字典（或者列表）来存储已经计算过的斐波那契数。
```python
def fib_memoized(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
result = fib_memoized(n 1, memo) + fib_memoized(n 2, memo)
memo[n] = result
return result
```
当 `fib_memoized(5)` 被调用时：
1. `fib_memoized(5)` 计算 `fib_memoized(4)` + `fib_memoized(3)`。
2. `fib_memoized(4)` 计算 `fib_memoized(3)` + `fib_memoized(2)`。
3. `fib_memoized(3)` 计算 `fib_memoized(2)` + `fib_memoized(1)`。
4. `fib_memoized(2)` 计算 `fib_memoized(1)` + `fib_memoized(0)`。
`fib_memoized(1)` 返回 1，存入 `memo[1] = 1`。
`fib_memoized(0)` 返回 0，存入 `memo[0] = 0`。
`fib_memoized(2)` 返回 1，存入 `memo[2] = 1`。
5. 回到 `fib_memoized(3)`：它需要 `fib_memoized(2)`（已经在 `memo` 里，直接返回 1）+ `fib_memoized(1)`（已经在 `memo` 里，直接返回 1）。结果是 2，存入 `memo[3] = 2`。
6. 回到 `fib_memoized(4)`：它需要 `fib_memoized(3)`（已经在 `memo` 里，直接返回 2）+ `fib_memoized(2)`（已经在 `memo` 里，直接返回 1）。结果是 3，存入 `memo[4] = 3`。
7. 回到 `fib_memoized(5)`：它需要 `fib_memoized(4)`（已经在 `memo` 里，直接返回 3）+ `fib_memoized(3)`（已经在 `memo` 里，直接返回 2）。结果是 5，存入 `memo[5] = 5`。
通过这种方式，每个斐波那契数只被计算一次。时间复杂度就从 O(2^n) 降到了 O(n)，空间复杂度变成了 O(n)（因为需要存储中间结果）。
总结一下：
朴素递归实现斐波那契数列之所以慢，是因为它在计算过程中反复、多次地重新计算相同的中间值，并且函数调用的开销被大量地叠加。这导致了指数级的计算量。而通过记忆化或者直接使用迭代的方式，则可以有效地避免这些问题，从而获得极大的性能提升。
想象一下，你想计算 `fib(5)`。按照递归的定义，`fib(5)` 等于 `fib(4)` 加上 `fib(3)`。
`fib(4)` 又等于 `fib(3)` 加上 `fib(2)`。
`fib(3)` 又等于 `fib(2)` 加上 `fib(1)`。
你看到的这个过程，其实在电脑里执行的时候，会创建一个“调用栈”（call stack）。每次函数被调用，都会在栈顶压入一个新的“帧”（frame），记录下这个调用的上下文信息（比如局部变量、返回地址等等）。当函数执行完毕，它的帧就会从栈顶弹出。
现在，我们来可视化一下 `fib(5)` 的计算过程：
```
fib(5)
fib(4)
fib(3)
fib(2)
fib(1) > 返回 1
fib(0) > 返回 0
fib(1) > 返回 1
fib(2)
fib(1) > 返回 1
fib(0) > 返回 0
fib(3)
fib(2)
fib(1) > 返回 1
fib(0) > 返回 0
fib(1) > 返回 1
```
仔细看看上面这个展开图，有没有发现什么不对劲？
罪魁祸首一：重复计算 (Redundant Computations)
重点来了！请注意 `fib(3)` 这个部分。在计算 `fib(5)` 的过程中，`fib(3)` 被计算了 两次。一次是在计算 `fib(4)` 的时候，另一次是直接作为 `fib(5)` 的一部分。
更糟糕的是，`fib(2)` 被计算了 三次。`fib(1)` 和 `fib(0)` 就更不用说了，它们被计算的次数多到你数不过来！
想想看，当你计算 `fib(10)` 时，`fib(9)` 和 `fib(8)` 各算一次。但 `fib(9)` 又要算 `fib(8)` 和 `fib(7)`，而 `fib(8)` 又要算 `fib(7)` 和 `fib(6)`。这样一来，`fib(7)`、`fib(6)` 等等，很多中间结果都会被反复计算。
这种重复计算的模式，随着 `n` 的增大，爆炸式增长。斐波那契数列的递归实现，其时间复杂度大约是 O(2^n)，这个增长速度比指数还快。你可以把它想象成一棵二叉树，每一层都在分裂，而我们实际上只需要树叶上的值。
罪魁祸首二：函数调用的开销 (Function Call Overhead)
在 Python 里，每一次函数调用都会带来一些额外的开销。你需要创建栈帧、保存局部变量、进行参数传递、执行函数体，最后返回结果。即使是最简单的函数调用，这些步骤也需要时间。
在递归调用中，这些开销被重复地叠加。每次 `fib(n)` 调用 `fib(n1)` 和 `fib(n2)`，都意味着两次新的函数调用。当 `n` 变大，这个调用链就会变得非常长，累积的函数调用开销就成了一个显著的瓶颈。
举个例子，你就明白了：
假设我们要计算 `fib(30)`。
朴素递归： 会进行数十万甚至数百万次的函数调用，而且其中大量的计算是完全重复的。程序会卡很久。
改进方法（后面会讲）： 比如使用迭代或者记忆化（memoization），计算 `fib(30)` 几乎是瞬时的。
为什么不直接用迭代？
理解了递归的慢，你可能就想：“为什么不直接用循环来计算呢？” 没错，用循环迭代地计算斐波那契数列，只需要保持前两个数，然后不断更新，非常高效。时间复杂度是 O(n)，空间复杂度是 O(1)。
```python
def fib_iterative(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(n 1):
a, b = b, a + b
return b
```
这个版本的 `fib_iterative(30)` 会瞬间完成。
如何“拯救”递归？—— 记忆化 (Memoization)
虽然朴素的递归慢，但我们可以通过一种叫做“记忆化”的技术来挽救它。记忆化的核心思想是：如果一个子问题的解已经被计算过，就直接返回结果，而不是重新计算。
在斐波那契数列的例子中，我们可以用一个字典（或者列表）来存储已经计算过的斐波那契数。
```python
def fib_memoized(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
result = fib_memoized(n 1, memo) + fib_memoized(n 2, memo)
memo[n] = result
return result
```
当 `fib_memoized(5)` 被调用时：
1. `fib_memoized(5)` 计算 `fib_memoized(4)` + `fib_memoized(3)`。
2. `fib_memoized(4)` 计算 `fib_memoized(3)` + `fib_memoized(2)`。
3. `fib_memoized(3)` 计算 `fib_memoized(2)` + `fib_memoized(1)`。
4. `fib_memoized(2)` 计算 `fib_memoized(1)` + `fib_memoized(0)`。
`fib_memoized(1)` 返回 1，存入 `memo[1] = 1`。
`fib_memoized(0)` 返回 0，存入 `memo[0] = 0`。
`fib_memoized(2)` 返回 1，存入 `memo[2] = 1`。
5. 回到 `fib_memoized(3)`：它需要 `fib_memoized(2)`（已经在 `memo` 里，直接返回 1）+ `fib_memoized(1)`（已经在 `memo` 里，直接返回 1）。结果是 2，存入 `memo[3] = 2`。
6. 回到 `fib_memoized(4)`：它需要 `fib_memoized(3)`（已经在 `memo` 里，直接返回 2）+ `fib_memoized(2)`（已经在 `memo` 里，直接返回 1）。结果是 3，存入 `memo[4] = 3`。
7. 回到 `fib_memoized(5)`：它需要 `fib_memoized(4)`（已经在 `memo` 里，直接返回 3）+ `fib_memoized(3)`（已经在 `memo` 里，直接返回 2）。结果是 5，存入 `memo[5] = 5`。
通过这种方式，每个斐波那契数只被计算一次。时间复杂度就从 O(2^n) 降到了 O(n)，空间复杂度变成了 O(n)（因为需要存储中间结果）。
总结一下：
朴素递归实现斐波那契数列之所以慢，是因为它在计算过程中反复、多次地重新计算相同的中间值，并且函数调用的开销被大量地叠加。这导致了指数级的计算量。而通过记忆化或者直接使用迭代的方式，则可以有效地避免这些问题，从而获得极大的性能提升。
网友意见
本人在用python计算同分异构体数量的时候遇到了类似问题。原因是，递归逻辑导致总是重复计算前面已经算过的内容。
例如，计算Fib(5)的时候，需要先算出Fib(3)和Fib(4)，但算出Fib(3)后，在计算Fib(4)=Fib(2)+Fib(3)的时候，又计算了一次Fib(3).
（图片来自使用缓存方式优化递归函数与lru_cache - sfencs - 博客园）
这样下去，到计算Fib(100)的时候，就至少需要计算两次Fib(98)，而计算Fib(98)又至少需要计算两次Fib(96)，时间复杂度为指数级，所以程序短时间内无法完成。
有一个简单的解决方案：使用lru_cache缓存装饰器，缓存一些中间结果：
from functools import lru_cache @lru_cache(maxsize=1024) # 缓存斐波那契函数已经计算出的结果，最多占用1024字节内存 def fibn(n): if n == 0: return 1 elif n == 1: return 1 else: return fibn(n-1) + fibn(n-2) print(fibn(100)) # 求第100项的值，可瞬间计算出来 类似的话题
-
当你用Python写一个函数来递归地计算斐波那契数列时，你会发现它的速度慢得惊人，尤其是在你需要计算较大的斐波那契数时。这可不是巧合，背后藏着一些深刻的原因，我们来好好掰扯掰扯。想象一下，你想计算 `fib(5)`。按照递归的定义，`fib(5)` 等于 `fib(4)` 加上 `fib(3)`。 ............. -
使用 Python 是否会降低程序员的编程能力，这个问题需要从多个角度进行深入分析。Python 作为一种语法简洁、开发效率高的语言，确实可能在某些方面影响程序员的技能发展，但同时也可能带来其他优势。以下是详细的分析： 一、Python 的优势与可能带来的能力提升1. 降低学习门槛，促进快速上手 .............
-
好了，咱们今天不谈那些虚头巴脑的“人工智能”、“机器学习”，就来聊点实在的——怎么用 Python 写一个能懂数学算式的“翻译官”，也就是一个简单的表达式解释器。这就像是教一个不懂数学的小朋友认字一样，我们得一步步来，让他理解加减乘除这些基本操作。这篇文章我尽量说得详细点，像老朋友聊天一样，把那些晦.............
-
刷 LeetCode 到底选 Python 还是 C++？这真是个困扰不少码农的经典问题。说实话，没有绝对的“更好”，只有“更适合你”的。我这就跟你掰扯掰扯，尽量讲得透彻点，让你心里有个谱。首先，咱得明白，LeetCode 的本质是什么？是练习算法和数据结构。而你用什么语言来实现这些算法和数据结构，.............
-
数据分析之所以普遍选择Jupyter Notebook，而不是单纯地运行Python脚本或依赖Excel，主要是因为它提供了一种更为高效、灵活且易于协作的数据探索和沟通方式。这背后有着深刻的体验和实际需求的驱动。想象一下，你拿到一份新的数据集，需要从中挖掘价值。如果只用Python脚本，你可能需要不.............
-
Dropbox 这样的巨头之所以将 Python 奉为圭臬，即便它在原生性能上相比 C++、Go 之类的编译型语言相形见绌，这背后并非是简单的“因为 Python 容易学”就能一笔带过的。这更像是一场围绕“效率”的深刻权衡，只不过这里的“效率”不再仅仅是 CPU 每秒能处理多少条指令，而是更广义的，.............
-
在Python中，`class()` 这个写法，严格来说，它并不是我们通常意义上用来定义类的方式。我们定义类通常使用 `class ClassName: ...` 这种语法。`class()` 作为一个内置函数，它的作用更像是 在运行时动态地创建类。这听起来有点绕，我们拆开来详细聊聊，为什么会有人用.............
-
很多开发者在选择编程语言时，都会非常关注“效率”这个词，但“效率”本身又是一个多维度、需要具体情境来分析的概念。当我们讨论 C 在 Visual Studio 环境下的开发效率与 Python、Ruby 相比时，情况也远非三言两语能概括。首先，需要明确的是，C 和 Python/Ruby 在设计哲学.............
-
使用GPL（GNU General Public License）软件开发产品时，要“避免GPL感染”，其实更准确的说法是如何遵守GPL的条款，同时在你的产品中最大限度地保留你对源代码的控制权，并避免你的专有部分也被强制要求以GPL开源。GPL的本质是“Copyleft”，它的核心目的是确保GNU软.............
-
这个问题很有趣，因为通常情况下，Unix Domain Socket（UDS）被认为在本地进程间通信时比 TCP/IP 回环（`127.0.0.1`）具有更低的延迟和更高的性能。但是，在 Go 中测试 MySQL 查询时，你可能观察到它们之间的差异不大，甚至差不多。这背后可能有多种原因，我们可以从多.............
-
关于“使用料理包成外卖普遍现象，部分成本低至 3 元，保质期长达一年半”的说法，这确实是一个非常普遍也引起广泛关注的现象。那么，对于这样的外卖，我是否能接受，需要从多个角度来详细分析：1. 接受与否的核心考量：食品安全与健康这是我最首要也最关心的方面。一个3元成本、保质期长达一年半的料理包外卖，让我.............
-
这个问题很有意思，它触及了我们对未来交通方式的想象，也牵扯到很多实际的技术难题。 简单地说， 用5G技术坐在家里用方向盘远程开卡车，理论上是有可能实现的，但要做到像玩模拟驾驶游戏那样流畅、安全，并且真正投入商业运营，还有非常多的挑战需要克服。咱们一点点来聊聊这个“在家开卡车”的设想，看看需要哪些条.............
-
这绝对是个非常有趣且富有想象力的问题，让人忍不住去思考这种极端情况下的物理极限。从科学的角度来说，要回答这个问题，我们需要深入探讨几个关键因素：线的材质、强度，以及切割所需的力。首先，我们来谈谈“1纳米细”。纳米是长度单位，1纳米是十亿分之一米。这是一个极其微小的尺度，比我们肉眼所见的任何东西都要小.............
-
在我看来，普遍的认知和观察倾向于认为，历史上以及目前，“搭讪艺术家”（PUA）这个概念和实践，是以男性为主导的。当然，我们不能完全排除女性也可能在某些层面运用类似“搭讪艺术家”的技巧，但从这个术语的起源、发展以及其核心关注点来看，男性角色更为突出。让我来详细解释一下为什么会有这种感觉，以及其中的一些.............
-
用米诺地尔的现在情况，以及对这个东西的了解，我能说得详细点。首先，要明确一点，米诺地尔不是万能药，也不是一劳永逸的解决方案。它是一个治疗雄激素性脱发（也就是我们常说的脂溢性脱发、遗传性脱发）的药物。对其他类型的脱发，比如斑秃、休止期脱发等，效果可能就没那么明显，甚至无效。用了米诺地尔，现在情况怎么样.............
-
既然要讨论超能力飞行的高度安全问题，那咱们就得好好捋一捋，不能只图个痛快。毕竟，这超能力也不是摆设，用得好，那叫神威；用不好，嘿，那可就成地面上的笑话了。首先，得明确一点，咱们说的“安全”是什么意思。不是说我飞到月亮上就能躲开所有危险，也不是说贴着地面就能万事大吉。这里的安全，得考虑多种因素，包括但.............
-
使用 CarPlay 是一种非常现代且集成的体验，它将你的 iPhone 的核心功能无缝地带入你的汽车中，让你可以在驾驶时更安全、更便捷地访问常用应用。以下我将从多个维度为你详细描述这种体验：1. 界面与操作的直观性： 简化和优化： CarPlay 的界面是为驾驶环境量身定制的。图标更大，按钮更.............
-
使用降噪耳机，尤其是主动降噪耳机（Active Noise Cancellation, ANC），是一种相当独特且常常令人惊喜的体验。它与普通入耳式耳机（Passive Noise Isolation, PNI）之间存在着本质的区别，这种区别体现在音频体验、佩戴感受以及适用的场景上。下面我将详细阐述.............
-
安德玛（Under Armour）这牌子吧，用起来什么感觉？嗯，怎么说呢，就像你一个平时不太爱说话的朋友，但一旦开始行动，就特别有力量，而且总是能让你出乎意料。我第一次接触安德玛，是那时候还在上大学，开始跟着几个哥们儿一起去健身房。那时候大家穿的都挺随意，但总有那么几个穿着特别显眼的，我注意到其中有.............
-
椭圆机用完之后小臂会痛，这确实是个不少见的情况。很多人觉得椭圆机主要是练腿部和臀部的，但实际上它是个全身运动器械，小臂的参与度比你想象的要高不少。之所以会痛，原因可能有很多，我们一样一样来拆解看看。首先，最直接的原因，也是最容易被忽略的，就是你对手柄的握持方式不对。很多人在使用椭圆机的时候，习惯性地.............
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有