为什么这个递归解决方案比迭代解决方案更快？

Question

我今天为某事写了一个递归解决方案，而随着它的发展，好奇心使我走上了一条奇怪的道路。我想看看优化的递归解决方案与迭代解决方案相比如何，所以我选择了一个经典的 Nth Fibonacci 来测试。

我惊讶地发现带记忆的递归解决方案比迭代解决方案快得多，我想知道为什么。

这是代码（使用 python3）：

import time
import sys
sys.setrecursionlimit(10000)

## recursive:
def fibr(n, memo = {}):
    if n <= 1:
        return n

    if n in memo:
        return memo[n]

    memo[n] = fibr(n-1, memo) + fibr(n-2, memo)

    return memo[n]

## iterative:
def fibi(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

rstart = time.time()
for n in range(10000):
    fibr(n)
rend = time.time()

istart = time.time()
for n in range(10000):
    fibi(n)
iend = time.time()

print(f"recursive: {rend-rstart}")
print(f"iterative: {iend-istart}")

我的结果：

recursive: 0.010010004043579102
iterative: 6.274333238601685

除非我弄错了，否则递归解决方案和迭代解决方案都已尽可能优化？如果我错了，我想知道为什么。

如果不是，是什么导致迭代解决方案如此缓慢？ n 的所有值似乎都比较慢，但当 n 更合理时更难注意到，例如 <1000。（我正在使用 10000，如上所示）

我尝试过的一些东西：

我认为这可能是迭代解决方案中的神奇交换a, b = b, a + b，所以我尝试用更传统的“交换”模式替换它：

tmp = a + b     
a = b           
b = tmp         
#a, b = b, a + b

但是结果基本一样，所以不是问题所在。

重新安排代码，让迭代解决方案先运行，只是为了看看 OS 级别是否存在一些奇怪的缓存问题？它不会改变结果，所以不是吗？

我在这里的理解（可能是错误的）是带记忆的递归解决方案是O(n)。并且迭代解也是 O(n) 只是因为它从 0..n.

迭代

我是不是漏掉了一些很明显的东西？我觉得我一定在这里遗漏了一些东西。

Answer 1

它们不一样。

递归版本使用 Memoization 模式，只计算一次 fibr(n) 的结果，storing/caching 如果需要再次计算 insta-return 的结果。这是一个 O(n) 算法。

迭代版本从头计算一切。这是一个 O(n2) 算法（我认为）。

Answer 2

您可能期望 def fibr(n, memo = {}): — 在没有提供 memo 的情况下调用时 — 变成翻译成有点像的东西：

def _fibr_without_defaults(n, memo):
   ...

def fibr(n):
    return _fibr_without_defaults(n, {})

也就是说，如果缺少 memo，它会根据您的默认值隐式获得一个空白词典。

In actuality，它翻译成更像：

def _fibr_without_defaults(n, memo):
   ...

_fibr_memo_default = {}
def fibr(n):
    return _fibr_without_defaults(n, _fibr_memo_default)

也就是说，默认参数值不是“使用它来构造默认值”，而是“默认使用这个实际值”。您对 fibr 的每次调用（不提供 memo）都是共享默认 memo 字典。

这意味着在：

for n in range(10000):
    fibr(n)

循环的先前迭代正在为将来的迭代填充 memo。例如，当 n 为 1000 时，仍然存储 n<=999 执行的所有工作。

相比之下，迭代版本总是从 0 开始迭代，无论之前的迭代调用执行了什么工作。

如果您手动执行上述翻译，那么每次调用都会得到一个新的空 memo，您会发现迭代版本更快。（有道理；将东西插入字典并检索它们只是为了做与简单迭代相同的工作会更慢。）

为什么这个递归解决方案比迭代解决方案更快？

Why is this recursive solution faster than the iterative solution?

python

iteration

optimization

recursion