斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

分析

解法一：

• 递归

  当n==0时，F(n)=0。

  当n==1时，F(n)=1。

  当n>=2时，F(n)=F(n-1)+F(n-2)。

  # -*- coding:utf-8 -*-
  class Solution:
      def Fibonacci(self, n):
          if n<0:
              return None
          elif n==0:
              return 0
          elif n==1:
              return 1
          else:
              return self.Fibonacci(n-1)+self.Fibonacci(n-2)
  

• 缺点：算法时间复杂度过大。

解法二：

• 递推循环

  # -*- coding:utf-8 -*-
  class Solution:
      def Fibonacci(self, n):
          if n<0:
              return None
          elif n==0:
              return 0
          elif n==1:
              return 1
          else:
              a = 0
              b = 1
              for i in range(n-1):
                  Fn = a + b
                  a = b
                  b = Fn
              return Fn