python - 为什么 Fibonacci 迭代比递归版本(带内存)慢？

Question

我正在比较 Python 3 中斐波那契例程的两个版本:

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

第一个版本是递归的，带有内存(感谢 lru_cache)。第二种是简单的迭代。

然后我对这两个版本进行了基准测试，我对结果感到有些惊讶:

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)

迭代版本比递归版本慢很多。当然第一次运行递归版本会花很多时间(缓存所有结果)，递归版本占用更多内存空间(存储所有调用)。但我没想到在运行时会有这样的差异。与仅遍历数字和交换变量相比，调用函数不会产生一些开销吗？

Answer 1

如您所见，timeit 多次调用该函数，以获得可靠的测量结果。递归版本的 LRU 缓存不会在调用之间被清除，因此在第一次运行后，fibonacci_rec(1000) 只是立即从缓存中返回，而不进行任何计算。