斐波那契数列实现方式,以及递归和非递归时间对比

第n个斐波那契数是多少..递归方式

1 def fib(n):
2     if n== -1:
3         exit()
4     elif n<3:
5         return 1
6     else:
7         return fib(n - 1) + fib(n - 2)
8 print(fib(100))

第n个斐波那契数是多少..非递归方式

1 def fib(n):
2     re = [0,1]
3     if n <=1:
4         return re[n]
5     for i in range(2,n+1):
6         re.append(re[i-1]+re[i-2])
7     return re[n]
8 print(fib(100))

n以内的斐波那契数都列出来

1 def fib(n):
2     a, b = 1, 1
3     while a < n:
4         print(a, end=' ')
5         a, b = b, a+b
6     print()
7 fib(1000)

最后..递归很好资源.后面时间成指数增加

 1 import datetime
 2 
 3 start = datetime.datetime.now()
 4 def fib(n):
 5     re = [0,1]
 6     if n <=1:
 7         return re[n]
 8     for i in range(2,n+1):
 9         re.append(re[i-1]+re[i-2])
10     return re[n]
11 print(fib(1000))
12 end = datetime.datetime.now()
13 print(end-start)
14 
15 print("*"*30)
16 
17 start = datetime.datetime.now()
18 def fib(n):
19     if n== -1:
20         exit()
21     elif n<3:
22         return 1
23     else:
24         return fib(n - 1) + fib(n - 2)
25 print(fib(40))
26 
27 end = datetime.datetime.now()
28 print(end-start)

结果对照..

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
0:00:00.000999
******************************
102334155
0:00:47.448738

注意,,非递归查的是第1000个,递归查的是第40个..但是时间差距巨大