为何带记忆化的递归斐波那契算法比迭代版更快？

这事儿确实有点反直觉，我来给你拆解下背后的核心原因：

首先先明确你的实现代码和测试结果：

你的实现代码 #

import functools
@functools.lru_cache()
def fibonacci_rec(target: int) -> int:
    if target < 2:
        return target
    res = fibonacci_rec(target - 1) + fibonacci_rec(target - 2)
    return res

def fibonacci_it(target: int) -> int:
    if target < 2:
        return target
    n_1 = 2
    n_2 = 1
    for n in range(3, target):
        new = n_2 + n_1
        n_2 = n_1
        n_1 = new
    return n_1

你的基准测试结果 #

In [5]: %timeit fibonacci_rec(1000)
82.7 ns ± 2.94 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [6]: %timeit fibonacci_it(1000)
67.5 µs ± 2.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

核心原因：缓存带来的O(1) vs 迭代的O(n) #

你提到的“递归首次运行会缓存结果”是关键，但你可能没注意到%timeit的运行逻辑：它会重复执行目标代码很多次来取平均时间。

• 对于fibonacci_rec(1000)，第一次调用会计算所有斐波那契值并写入缓存，但从第二次调用开始，直接从lru_cache维护的哈希表里取出缓存好的结果——这本质是一个O(1)的哈希查找操作，速度快到离谱。
• 而fibonacci_it(1000)每次调用都要从头开始循环近1000次，每次循环都要执行加法、变量赋值操作，这是实打实的O(n)时间复杂度，几百次循环的开销累加起来，自然比一次缓存查找慢得多。

关于“函数调用开销”的误区 #

你担心的“函数调用额外开销”其实在这个场景下几乎可以忽略：

• 现代Python对函数调用的优化已经非常成熟，单次函数调用的开销极低；
• 更重要的是，当缓存命中时，fibonacci_rec几乎没做什么逻辑——它甚至不会进入递归分支，直接返回缓存值，函数内部的判断逻辑都执行得极快，和迭代的循环开销根本不在一个量级。

验证结论的小技巧 #

如果你想看到递归首次计算的真实耗时，可以清空缓存后用%time（只跑一次）测试：

fibonacci_rec.cache_clear()
%time fibonacci_rec(1000)

这时候你会发现递归的首次调用时间明显比迭代长，因为它要计算所有中间值并写入缓存；而迭代版本每次运行的时间都差不多，因为它每次都要从头循环。

内容的提问来源于stack exchange，提问作者JPFrancoia