本文算法使用python3实现

---

1.题目描述：

  大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

  时间限制：1s；空间限制：32768K

---

2.思路描述：

  实现斐波那契额数列主要有两种方法：

  （1）递归法：自顶向下进行，当递归较深时，时间复杂度是很高的。

  （2）迭代法：自底向上进行，从第0项开始计算，并将结果保存起来，最后返回第n项即可。该方法时间复杂度较低，但需要额外空间，相对于递归来说，是一种空间换时间的方法。

  接下来我们将分别对两种方法进行实现，并比较两者的时间消耗。

---

3.程序代码：

递归法

class Solution:    def Fibonacci(self, n):        '''递归法'''        if n in [0,1]:            return n        return self.Fibonacci(n-2)+self.Fibonacci(n-1)

所需时间：

  

迭代法

class Solution:    def Fibonacci(self, n):        '''迭代法'''        FibList = []        # 将前n项保存在数组中        for i in range(n+1):            if i in [0,1]:                FibList.append(i)                continue            FibList.append(FibList[-2]+FibList[-1])        return FibList[-1]

所需时间：