Python算法题----玩转fibonacci数列

qns_fengyusong

　　fibonacci数列是个很常见的面试题，相信大家都见识过，反正我碰见过两次。递归是最容易想到的办法。但是写一个递归，往往面试官并不满意，会追问。这个递归存在什么问题啊。有没有其它办法啊……。办法总比问题多，跳跳大路通帝都。下面就总结一下。把程序写到面试官的心缝里！
　　递归法
　　这个递归存在的最严重的问题就是重复计算，在代码的递归分支里可以看到函数被递归调用了两次，那么很多函数其实都被重复计算了。最后再来解决这个问题。
def fib01(n):　　
    if n == 1 or n == 2:
　　
        return n
　　
    else:
　　
        return fib01(n-1) + fib01(n-2)
　　递推法1
　　使用一个列表来存储整个fibonnci数列，所求的即为列表的第n项
def fib02(n):　　
    if n == 1 or n == 2:
　　
        return n
　　
    else:
　　
        arr = [1, 1, 2]
　　
        i = 3
　　
        for i in range(3, n+1):
　　
            arr.append(arr[i-1] + arr[i-2])
　　
        return arr[n]
　　递推法2
　　声明几个历史变量不断计算数列的值，并且交换变量
def fib03(n):　　
    if n == 1 or n == 2:
　　
        return n
　　
    else:
　　
        x = 1
　　
        y = 2
　　
        for i in range(3, n+1):
　　
            fi = x + y
　　
            x = y
　　
            y = fi
　　
        return y
　　缓存递归中间结果
　　定义一个字典，将递归函数的计算结果存入_fib_cache，每次判断该函数是否在缓存中，在直接返回，不在，计算并放入缓存
_fib_cache = {}　　
def fib04(n):
　　
    if n in _fib_cache:
　　
        return _fib_cache[n]
　　
    else:
　　
        _fib_cache[n] = n if n <= 2 else fib04(n-1) + fib04(n-2)
　　
        return _fib_cache[n]
　　有了缓存，生活美好了很多，但是看着有点别扭。孤零零的_fib_cache，弄个装饰器多好，这明显可以有个装饰器的。
　　函数装饰器
def memo(f):　　
    cache = {}
　　

　　
    def decorated(*args):
　　
        if args in cache:
　　
            return cache[args]
　　
        else:
　　
            cache[args] = f(*args)
　　
            return cache[args]
　　

　　
    return decorated
　　有了这个装饰器函数，我们就可以装饰我们的递归函数了
@memo　　
def fib01(n):
　　
    if n == 1 or n == 2:
　　
        return n
　　
    else:
　　
        return fib01(n-1) + fib01(n-2)