詳解python中遞歸函數(shù)

更新時間：2019年04月16日 17:29:48 作者：都枯槐

這篇文章主要介紹了python遞歸函數(shù)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

函數(shù)執(zhí)行流程

def foo1(b,b1=3):
   print("foo1 called",b,b1)
 
 def foo2(c):
    foo3(c)
    print("foo2 called",c)
 def foo3(d):
   print("foo3 called",d)
 def main():
   print("main called")
   foo1(100,101)
   foo2(200)
   print("main ending ")

函數(shù)執(zhí)行過程：

全局幀中生成foo1、foo2、foo3、main函數(shù)對象
main函數(shù)調(diào)用
main中查找內(nèi)建函數(shù)print壓棧，將常量字符串壓棧，調(diào)用函數(shù)，彈出棧頂，返回值。
main中全局查找foo1壓棧，將常量100、101壓棧，調(diào)用函數(shù)foo1，創(chuàng)建棧幀。print函數(shù)壓棧，字符串和變量b、b1壓棧，調(diào)用函數(shù)，彈出棧頂，返回值。
main中全局查找foo2函數(shù)壓棧，將常量200壓棧，調(diào)用foo2，創(chuàng)建棧幀。foo3函數(shù)壓棧，變量c引用壓棧，調(diào)用foo3函數(shù)，創(chuàng)建棧幀，foo3中內(nèi)建函數(shù)中查找print壓棧，將字符常量和變量d壓棧。foo3完成print函數(shù)調(diào)用后返回。foo2恢復(fù)調(diào)用，執(zhí)行print后，返回值，main中foo2調(diào)用結(jié)束后彈出棧頂，main繼續(xù)執(zhí)行print函數(shù)調(diào)用，彈出棧頂，main函數(shù)返回

函數(shù)中壓棧,執(zhí)行流程。

遞歸Recursion

函數(shù)直接或者間接調(diào)用自身就是遞歸
遞歸需要有邊界條件、遞歸前進(jìn)段，遞歸返回段
遞歸一定需要有邊界條件
當(dāng)邊界條件不滿足的時候，遞進(jìn)前進(jìn)
當(dāng)邊界條件滿足的時候，遞歸返回

遞歸要求

遞歸一定要有退出條件，遞歸調(diào)用一定執(zhí)行到這個退出條件。沒有退出條件的遞歸調(diào)用，就是無限調(diào)用
遞歸調(diào)用的深度不宜過深
python對遞歸調(diào)用的深度做了限制，以保護(hù)解釋器，cpython中遞歸深度為1000，ipython中遞歸深度為3000
超過遞歸深度限制，拋出RecursionError:maxinum recursion depth exceeded 超出最大深度
sys.getrecursionlimit()是顯示最大限制
對于基于前面或者換位置的時候使用封裝和解構(gòu)更有效

斐波那契數(shù)列實現(xiàn)（f(1)=1,f(2)=1,f(3)=f(1)+f(2),f(4)=f(2)+f(3)……）

#斐波那契數(shù)列普通循環(huán)實現(xiàn)
a,b=0,1
for i in range(4):
  a,b=b,a+b
print(a)

#斐波那契數(shù)列函數(shù)遞歸實現(xiàn)
def foo(n): #大量的重復(fù)計算
   return 1 if n<3 else foo(n-1)+foo(n-2) 
 
#斐波那契數(shù)列函數(shù)循環(huán)實現(xiàn)
def fn(n,a=0,b=1):
  a,b=b,a+b
  if n==1:
    return a
  return fn(n-1,a,b)

遞歸的性能

循環(huán)稍微復(fù)雜一些，但是只要不是死循環(huán)，可以多次迭代直至算出結(jié)果
遞歸還有深度限制，如果遞歸復(fù)雜，函數(shù)反復(fù)壓棧，棧內(nèi)存很快會溢出

間接遞歸

def foo1():
  foo2()
def foo2():
  foo1()

間接遞歸，是通過別的函數(shù)調(diào)用了函數(shù)自身，但是如果構(gòu)成了循環(huán)遞歸調(diào)用是非常危險的，但是往往這種情況在代碼復(fù)雜的情況下，還是有可能發(fā)生這種調(diào)用的，要用代碼的規(guī)范來避免這種遞歸調(diào)用的發(fā)生

遞歸總結(jié)

遞歸是一種很自然的表達(dá)，符合邏輯思維
遞歸相對運行效率低，每一次調(diào)用函數(shù)都要開辟新的棧幀
遞歸有深度限制，如果遞歸層次太深，函數(shù)反復(fù)壓棧，棧內(nèi)存很快就溢出了
如果是有限次數(shù)的遞歸，可以使用遞歸調(diào)用，或者使用循環(huán)代替，循環(huán)代碼稍微復(fù)雜一些，但是只要不是死循環(huán)，過次迭代直至算出結(jié)果
絕大多數(shù)遞歸，都可以使用循環(huán)實現(xiàn)
即使遞歸代碼很簡潔，能不用盡量不使用遞歸

以上所述是小編給大家介紹的python遞歸函數(shù)詳解整合，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！

您可能感興趣的文章: