斐波那契數列

當年，典型的遞歸題目，斐波那契數列還記得嗎？

def fib(n):

if n==1 or n==2:

return 1

else:

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

當然, 為了程序健壯性，加上try...except...

def fib(n):

if isinstance(n, int):

print('兄弟,輸入正整數哈')

return

try:

if n==1 or n==2:

return 1

elif n <= 0:

print('兄弟別輸入0或負數呀')

else:

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

except RecursionError:

print('兄弟，超過了最大遞歸深度'

是的，無論時間還是空間復雜度，遞歸真的是不太好使哈！這是遞歸的寫法:

def fib(n):

if n==1 or n == 2:

return 1

a, b = 1, 1

for i in range(2, n):

a, b = b, a+b

return b

我稍微解釋三點：

為啥是range(2, n)，因為，斐波那契數列從?1 開始，所以?fib(n) 就是數列的第?n 項

由于前兩項都為?1 ,所以要少兩項，為?range(2, n)(要循環?n-2 次)

a, b = b, a+b 這里你也許也有困惑，我簡單說說，一般Python解釋器會將逗號分隔的變量直接看做一個元組，

又因為，解釋器先執行等式右邊的，所以，這樣相當于?元組拆包

a, b = b, a+b 這句話的精髓在于，在等式右邊將?b 視為fib(n-2) ,將?a+b 視為?fib(n-1)

楊輝三角

同樣，先寫遞歸寫法(我這里不考慮特殊情況了，時間有限):

def YH_tri(a, b):

if a == b or b == 0:

return 1

else:

return YH_tri(a-1, b)+YH_tri(a-1, b-1)

老鐵們自己先想想該怎么寫？？

總結

以上所述是小編給大家介紹的提升Python效率之使用循環機制代替遞歸函數,希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對我們網站的支持！

如果你覺得本文對你有幫助，歡迎轉載，煩請注明出處，謝謝！

本文標題: 提升Python效率之使用循環機制代替遞歸函數

本文地址: http://www.cppcns.com/jiaoben/python/266539.html