Python递归和迭代实现求斐波那契数

Python实现求第N位斐波那契数。迭代用来队列来保存，用其它也是可以的。

#!/bin/env python
#coding:utf-8
from collections import deque
import datetime

# 递归版
def fibonacci(num):
    if num<=2:
        return 1
    else:
        return fibonacci(num-1)+fibonacci(num-2)

# 迭代版
def fibonacci2(num):
    s=deque()
    result=0
    for i in range(1,num+1):
        if i<=2:
            result=1
            s.append(result)
        else:
            result=s[0]+s[1]
            s.append(result)
            s.popleft()
    return result


n=40
print(datetime.datetime.now())
print('fibonacci(%d)=%d' % (n, fibonacci(n)))
print(datetime.datetime.now())
print('fibonacci2(%d)=%d' % (n, fibonacci2(n)))
print(datetime.datetime.now())

结果：

2017-05-19 18:00:52.194334
fibonacci(40)=102334155
2017-05-19 18:01:09.535270
fibonacci2(40)=102334155
2017-05-19 18:01:09.535328

递归效率还是比较底下，但是语法简明。