你看看你遞歸代碼的復雜度 是O(2^n) 而第二個的復雜度是O(n) 運行效率當然不同

COUNTER = 0

def fibn(n):

global COUNTER

COUNTER += 1

if n == 0:

return 1

elif n == 1:

return 1

else:

return fibn(n-1) + fibn(n-2)

statistics = []

for i in range(35):

COUNTER = 0

fibn(i + 1)

statistics.append(((i + 1), COUNTER))

print statistics[(1, 1), (2, 3), (3, 5), (4, 9), (5, 15), (6, 25), (7, 41), (8, 67), (9, 109), (10, 177), (11, 287), (12, 465), (13, 753), (14, 1219), (15, 1973), (16, 3193), (17, 5167), (18, 8361), (19, 13529), (20, 21891), (21, 35421), (22, 57313), (23, 92735), (24, 150049), (25, 242785), (26, 392835), (27, 635621), (28, 1028457), (29, 1664079), (30, 2692537), (31, 4356617), (32, 7049155), (33, 11405773), (34, 18454929), (35, 29860703)]

做了一個簡單的proflie

import cProfile

import pstats

def fibn(n):

if n == 0:

return 1

elif n == 1:

return 1

else:

return fibn(n-1) + fibn(n-2)

print ' i, calls, time'

for i in range(50):

pr = cProfile.Profile()

pr.enable()

fibn(i)

pr.disable()

stats = pstats.Stats(pr)

stats.strip_dirs()

st = stats.stats[('test1.py', 3, 'fibn')]

print '%3d,%10d,%8f' % (i, st[1], st[3])i, calls, time

0, 1, 0.000000

1, 1, 0.000001

2, 3, 0.000003

3, 5, 0.000005

4, 9, 0.000008

5, 15, 0.000012

6, 25, 0.000020

7, 41, 0.000033

8, 67, 0.000165

9, 109, 0.000088

10, 177, 0.000141

11, 287, 0.000228

12, 465, 0.000450

13, 753, 0.000601

14, 1219, 0.001016

15, 1973, 0.003561

16, 3193, 0.002593

17, 5167, 0.004372

18, 8361, 0.007097

19, 13529, 0.011073

20, 21891, 0.018552

21, 35421, 0.032467

22, 57313, 0.051762

23, 92735, 0.095383

24, 150049, 0.133490

25, 242785, 0.212390

26, 392835, 0.352861

27, 635621, 0.578204

28, 1028457, 0.987839

29, 1664079, 1.506812

30, 2692537, 2.682802

31, 4356617, 3.998936

32, 7049155, 8.089419

33, 11405773, 13.058235

34, 18454929, 23.930004

35, 29860703, 36.503880

目測fibn(50)要算出來需要兩周

總結

以上是生活随笔為你收集整理的递归函数斐波那契数列python_使用Python函数递归实现斐波那契数列时为什么运行速度很慢？...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。