一、斐波那契数列求第n项两种方式
1.递归（自上而下）
def recur_fibonacci(n):
if n <= 0:
return 0
if n == 1:
return 1 return recur_fibonacci(n - 1) + recur_fibonacci(n - 2) 2.循环（自下而上）
def loop_fibonacci(n):
a = 0
b = 1
l = [0] # 这里的l是把生成的斐波那契数列返回了
for i in range(n):
a, b = b, a + b
l.append(a)
return a, l
递归计算太慢，重复计算太多，时间复杂度是以n的指数方式递增，举个栗子：
from datetime import datetime start = datetime.now()
ret = recur_fibonacci(30)
end = datetime.now()
print(u'递归时间：%s'%(end - start).microseconds) start = datetime.now()
ret2 = loop_fibonacci(30)
end = datetime.now()
print(u'循环时间：%s'%(end - start).microseconds)
结果：
递归时间：
循环时间：
所以实际开发中还是用循环。
完。