Python斐波那契数列的实现

Fibonacci.py

def fabinacci(n):
    x,y = 0,1
    for index in range(n):
        x,y = x+y, x
    return x

def cache(fun):
    _cache = {}
    def _inner(n):
        if n in _cache:
           print(f"{n} in {_cache}")
        else:
            _cache[n] = fun(n)
        return _cache[n]
    return _inner
@cache
def f(n):
    '''
    http://www.gocalf.com/blog/calc-fibonacci.html
    时间复杂度为：T(n) = T(n - 1) + T(n - 2) + O(1)，很容易得到T(n) = O(1.618 ^ n)（1.618就是黄金分割，(1+5–√)/2(1+5)/2 ）。
    空间复杂度取决于递归的深度，显然是O(n)。
    '''
    if n == 0 or n == 1:
        return n
    else:
        return f(n-1) + f(n-2)
if __name__ == '__main__':
    for index in range(10):
        print(f"f({index}) = {f(index)}\n")