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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/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())

结果:

1
2
3
4
5
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

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

关注公众号 尹安灿