Python求斐波那契数列的第n项几种方法

在数学上，费波那契数列是以递归的方法来定义：

F（0）= 0
F（1）= 1
F（n）= F（n-1）+ F（n-2） （n >= 2）

特别指出：0不是第一项，而是第零项。

方法一：递归

递归的方法虽然简明清晰，但是开销太大，效率太低，会有大量的重复计算。

def Fibonacci(n):
    if n < 2:
        return n
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

方法二：递归的优化版本

优化版本的递归，把每次计算过的值都保存在字典中，避免大量重复计算。

known = {0:0, 1:1}
def Fibonacci(n):
    if n not in known:
        known[n] = Fibonacci(n-1) + Fibonacci(n-2)
    return known[n]

方法三：循环

能用递归实现的理论上也一定能用循环来实现，而且用循环实现，效率高，开销小。

def Fibonacci(n):
    prev, curr = 0, 1
    for _ in range(n):
        prev, curr = curr, prev+curr
    return prev

此方法时间复杂度O(n)，空间复杂度O(1)，是极佳的解决方案。