斐波那契數(shù)列

當(dāng)年，典型的遞歸題目，斐波那契數(shù)列還記得嗎？

            
def fib(n):
  if n==1 or n==2:
    return 1
  else:
    return fib(n-1)+fib(n-2)
          

當(dāng)然, 為了程序健壯性，加上 ?try...except...

            
def fib(n):
  if isinstance(n, int):
    print('兄弟,輸入正整數(shù)哈')
    return
  try:
    if n==1 or n==2:
      return 1
    elif n <= 0:
      print('兄弟別輸入0或負(fù)數(shù)呀')
    else:
      return fib(n-1)+fib(n-2)
  except RecursionError:
    print('兄弟，超過了最大遞歸深度'
          

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

            
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) ，因為，斐波那契數(shù)列從?1 開始，所以?fib(n) 就是數(shù)列的第?n 項?
• 由于前兩項都為?1 ,所以要少兩項，為? range(2, n) (要循環(huán)?n-2 次)
• a, b = b, a+b 這里你也許也有困惑，我簡單說說，一般Python解釋器會將逗號分隔的變量直接看做一個元組，?
• 又因為，解釋器先執(zhí)行等式右邊的，所以，這樣相當(dāng)于?元組拆包
• 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)
          

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

總結(jié)

以上所述是小編給大家介紹的提升Python效率之使用循環(huán)機制代替遞歸函數(shù),希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
如果你覺得本文對你有幫助，歡迎轉(zhuǎn)載，煩請注明出處，謝謝！