python实现斐波拉契数列

描述

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
由列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

这个数列从第3项开始，每一项都等于前两项之和。
如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)

递归版本

通过这个公式，容易想到第一个递归版本

def f(n):
        """递归版本 1"""
        return 1 if n <= 2 else f(n - 1) + f(n - 2)

递归版本 1 简单明了，但是存在很多冗余运算，导致运行效果堪忧。

def f(n):
        """递归版本 2"""
        cache = {1: 1, 2: 1}
        s = lambda n: cache.get(n) or cache.setdefault(n, s(n - 1) + s(n - 2))
        return s(n)

递归版本 2 通过字典避免了冗余元算，但是存在大量函数调用的开销。

def f(n, a=1, b=1):
        """递归版本 3"""
        return a if n <= 1 else f(n - 1, b, a + b)

递归版本 3 使用传参及默认参数，减少冗余元算的同时也减少了函数调用。

迭代版本

有递归版本，怎么少的了迭代版本

def f(n):
        """迭代版本 1"""
        lst = [1, 1]
        for i in range(2, n):
            lst.append(lst[i - 2] + lst[i - 1])
        return lst[-1]

迭代版本 1 通过一个列表存储了每次运算的结果，也很直观

def f(n):
        """迭代版本 2"""
        dct = {1: 1, 2: 1}
        for i in range(3, n + 1):
            dct[i] = dct[i - 1] + dct[i - 2]
        return dct[n]

迭代版本 2 和迭代版本 1 类似，使用字典而不是列表存储，占用空间更大

def f(n):
        """迭代版本 3"""
        a, b = 1, 1
        for _ in range(n - 2):
            a, b = b, a + b
        return b

迭代版本 3 较前面2个迭代版本，通过交换技巧，节省了空间，效率有了提升

公式版本

这个数列有通项公式，所以还可以来个公式版本

def f(n):
        """公式版本"""
        sqf = math.sqrt(5)
        return int(sqf / 5 * (math.pow(((1 + sqf) / 2), n) - math.pow(((1 - sqf) / 2), n)))

提示

python递归版本重新设置递归层数限制

import sys
sys.setrecursionlimit(1000000)

公式版本n较大时会引发溢出

OverflowError: math range error

总结

又想了个递归版本，利用了python中一个令人诟病的写法（可变类型作为默认参数）提升效率

def f(n, cache={1: 1, 2: 1}):
        """递归版本完全体"""
        return cache.get(n) or cache.setdefault(n, f(n - 2, cache) + f(n - 1, cache))

n=1000 时，千次执行时间（s）