斐波那契数列的多种实现方法（算法9）

问题：实现一函数，输入整数你，输出斐波那契数列的第n行。

这个问题很容易实现。有三种种思路：

（1）递归思路
根据斐波那契数列的定义不难写出递归形式的实现。但该递归实现会重复计算数列的各项，效率低。为此，可以添加缓存，保存已经计算过的项，但因此增加了空间复杂度。

（2）动态规划
根据斐波那契数列的地推形式，采用循环的方式实现

（3）利用数学定理
在数学上有以下定理：

（4）使用Python的迭代协议

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

由于上面的递归实现包括了重复计算的项，可以通过一个缓存保存已经计算过的项，以免每次都重复计算。另外一个问题是栈溢出，Python默认的栈大小是1000，超过1000就会出错。使用如下的方式改变。

import sys
sys.setrecursionlimit(10000)

添加了缓存的实现。

from functools import wraps

def cache(func):
    _cache = {}
	@wraps(func)
    def wrapper(n):
        if n in _cache:
            return _cache[n]
        r = func(n)
        _cache[n] = r
        return r
    return wrapper

@cache
def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

出于代码性能和简洁性，我们也可以使用Python标准库带的lru缓存算法。functools.lru_cache的实现采用C语言，性能比采用Python实现的高很多。

import functools

@functools.lru_cache(maxsize=2000)
def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

有了缓存后，修改递归深度限制可以轻易计算上万项的斐波那契数列。

import sys
sys.setrecursionlimit(10000)

fib(2048)

>>>4541530443743789425045571446290689202700908261293644428951182390278971452509283435684349718034771730433207742075010299663962500640783801879736380774181591579496806948995766259226048959686056348436218766394283482473000979306575217575924408151880646518264800221975575899556551648206461735151382670421151734360292599059971022927693971037208141410991471449358204418515391805517024
1694035610145547104337536614028338983073680262684101

上面的实现，计算复杂度以n的指数方式递增。空间复杂度为O(n)。下面采用循环实现。

在递归的思路上，不使用缓存（备忘录模式），还有一种尾递归思想，避免重复计算。

def _tail(n, c, a, b):
    if c == n-1:
        return b
    c += 1
    a, b = b, a + b
    return _tail(n, c, a, b)

def fib_tail(n):
    if n < 0:
        raise Exception("n must be zero or positive")
    if n in (0, 1):
        return 1
    c = 0
    a = b = 1
    return _tail(n, c, a, b)

1. 使用循环实现

首先根据f(0)和f(1)计算出f(2)，在根据f(1)和f(2)计算出f(3)，以此类推直到计算出f(n)。这样我们需要两个临时变量a和b，分别记录当前的f(n-1)和f(n)。

def fib(n):
    if n < 0:
        raise ValueError("n must be positive or zero")
    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a+b
    return b

该实现的时间复杂度为O(n)，空间复杂度为O(1)。还有一种思路其时间复杂度为O(logn)，但并不实用，通常用在科学计算上，这里不展开仅给出实现方法。

import numpy

def fib_with_numpy(n):
    if n <= 0:
        return 1
    c = _array = numpy.array([[1, 1], [1, 0]])
    for _ in range(n-1):
        c = c @ _array 
    return c[0][0]

（4）使用迭代协议的实现

在Python中实现迭代器协议要求类实现iter方法，且返回一个特殊的迭代器对象，这个迭代器对象实现了next方法，并且能通过抛出StopIteration异常来标识迭代器的完成。

class Fib:

def __init__(self):
        self.a = 0
        self.b = 1

def __iter__(self):
        return self

def __next__(self):
        value = self.b
        self.a, self.b = self.b, self.a + self.b
        return value

>>> from collections import Iterator
>>> isinstance(Fib(), Iterator)
True

>>> for i in Fib():
    print(i)
1
1
2
3
5
8
13