首页 › Python 实例 › 斐波那契数列

Python 斐波那契数列

数学实例 014

题目

斐波那契数列:0, 1, 1, 2, 3, 5, 8, 13…,从第三项起每一项等于前两项之和。用生成器输出前 20 项,并用缓存优化递归版本。

参考代码

from functools import lru_cache

def fib_gen(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

print("前 20 项:", list(fib_gen(20)))

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print("第 100 项:", fib(100))
执行以上代码输出结果为:
前 20 项: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
第 100 项: 354224848179261915075

代码解析

不加缓存的递归会重复计算大量子问题,fib(40) 就要算很久。@lru_cache 会记住已经算过的结果,让递归版本的复杂度降到线性。