为什么python递归效率低？

简单来讲

1。python是一个巨大的栈机器，进出栈可是非常耗时的（暂且不考虑是否io阻塞等问题）

2。运行递归的时候，单单对于斐波那契来说，相同的值都会重新计算一次（这也是优化的关键）

综上，一般来说，py的递归算法比迭代算法要慢。但是可能递归的语法更简洁

@functools.lru_cache()做“备忘”

原理根据上面的就大都晓得了，减少调用的次数改为直接查询。

这是标准库 functools里面的一个装饰器，要使用它，你得先impor

下面是原代码

def f(n):
    if n<2:
        return n
    return f(n-2)+f(n-1)

优化后....

import functools
@functools.lru_cache()
def f(n):
    if n<2:
        return n
    return f(n-2)+f(n-1)

以第20项为例子，即f(20)

原代码

1.52 ms ± 21.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

优化后

61.7 ns ± 1.08 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

注意！

这性能我估摸还跟你配置有关系。

该备忘装饰器是一个参数化装饰器，你可以百度获取更多，他还可以设置一下备忘的具体多少，还可以把1和1.0区分开。使用该装饰器时，他会在内部搞一个字典，字典特征还记得么，查找快，以空间换时间。