非递归实现斐波拉契函数

以下用递归和非递归实现斐波拉契函数，查看两种方法需要的时间。

# -*- coding:utf-8 -*-
import datetime
class Solution:
    '''
    要想非递归实现斐波拉契函数，只要保存f(n-2)、f(n-1)就可以，将其存入list中。
    当n=2时，只需要把list中的两个数相加一次即可，同时将相加的数存入list[1],将
    原来的list[1]存入list[0]中。
    '''
    def __init__(self):
        self.list=[0,1]

    def Fibonacci(self, n):
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            n-=1
            while n:
                temp=self.list[1]
                self.list[1] = self.list[0] + self.list[1]
                self.list[0]=temp
                n-=1
            return self.list[1]

class Solution_digui:

    def Fibonacci(self, n):
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            return self.Fibonacci(n-2)+self.Fibonacci(n-1)

i=datetime.datetime.now()
print Solution().Fibonacci(39)
j=datetime.datetime.now()
print j-i
print Solution_digui().Fibonacci(39)
k=datetime.datetime.now()
print k-j

输出：

63245986
0:00:00
63245986
0:00:40.448000

可以发现，非递归实现不到1秒，递归实现需要40多秒