Published on

python递归运行过慢的原因及解决方案

Authors
  • avatar
    Name
    Lif
    Twitter

今天用python编了一个斐波那契数列，代码如下：

def feb(i: int):
    if i == 0:
        return 1
    if i == 1:
        return 2
    return feb(i-2) + feb(i-1)
print(feb(73))

结果运行下去直接不出结果了，尝试把数值从73改到27后秒运行，看来是数值太大，运行时间过长…… python在运行递归的时候，每次用到之前的数值，都会重新计算一次……所以才会这么慢。 将结果放到缓存中，可以提高运行速度。

from functools import lru_cache
@lru_cache(maxsize=1024)
def feb(i: int):
    if i == 0:
        return 1
    if i == 1:
        return 2
    return feb(i-2) + feb(i-1)
print(feb(73))

这样运行73也可以秒出结果了！