斐波那契数列几种实现方式

今天在刷题时碰到了斐波那契额数列，然后发现有点忘记了，来记录一下几种实现方式。

递归法

def Fibonacci(i):
    if i <= 1:
        return i
    else:
        return Fibonacci(i-1) + Fibonacci(i-2)
 
if __name__ == "__main__":
    print(Fibonacci(100))

这种方法非常慢，有大量重复计算，复杂度是指数级

递推式

def Fibonacci(i):
   a, b = 0, 1
   for i in range(i):
       a, b = b, a+b
   return a
if __name__ == "__main__":
    for i in range(39):
        print(Fibonacci(i))

该方法复杂度是线性的

生成器

def Fibonacci(n):
   a, b = 0, 1
   while(n>0):
       a, b = b, a+b
       yield a
       n = n - 1
if __name__ == "__main__":
    for i in Fibonacci(10):
        print(i)

暂时记录三种方法。