Python 中的递归、记忆和可变默认参数

“Base”的意思是不只使用lru_cache。所有这些都“足够快”——我并不是在寻找最快的算法——但时间安排让我感到惊讶，所以我希望我能了解一些有关 Python 如何“工作”的知识。

简单循环（/尾递归）：

def fibonacci(n):
    a, b = 0, 1
    if n in (a, b): return n
    for _ in range(n - 1):
        a, b = b, a + b
    return b

简单记忆一下：

def fibonacci(n, memo={0:0, 1:1}):
    if len(memo) <= n:
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

使用发电机：

def fib_seq():
    a, b = 0, 1
    yield a
    yield b
    while True:
        a, b = b, a + b
        yield b

def fibonacci(n):
    return next(x for (i, x) in enumerate(fib_seq()) if i == n)

我预计第一个非常简单，是最快的。它不是。尽管存在递归和大量函数调用，但第二个是迄今为止最快的。第三个很酷，并且使用“现代”功能，但速度更慢，这令人失望。 （我很想将生成器视为在某些方面记忆化的替代方案 - 因为它们记住它们的状态 - 并且由于它们是用 C 实现的，我希望它们会更快。）

典型结果：

loop: about 140 μs
memo: about 430 ns
genr: about 250 μs

那么，谁能特别解释为什么记忆化比简单循环快一个数量级？

EDIT:

现在很清楚，我（像我之前的许多人一样）只是偶然发现了 Python可变的默认参数。这种行为解释了执行速度的实际和表面增益。

你所看到的就是记忆的全部意义。第一次调用该函数时，memo缓存为空，必须递归。但是下次您使用相同或更低的参数调用它时，答案已经在缓存中，因此它会立即返回。如果您执行数千个调用，则将第一个调用的时间分摊到所有其他调用的时间上。这就是记忆化成为如此有用的优化的原因，您只需第一次支付费用。

如果您想查看缓存新鲜时需要多长时间并且必须执行所有递归，您可以在基准测试调用中将初始缓存作为显式参数传递：

fibonacci(100, {0:0, 1:1})