詳解python中遞歸函數

函數執行流程

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 ")

函數執行過程：

1. 全局幀中生成foo1、foo2、foo3、main函數對象
2. main函數調用
3. main中查找內建函數print壓棧，將常量字符串壓棧，調用函數，彈出棧頂，返回值。
4. main中全局查找foo1壓棧，將常量100、101壓棧，調用函數foo1，創建棧幀。print函數壓棧，字符串和變量b、b1壓棧，調用函數，彈出棧頂，返回值。
5. main中全局查找foo2函數壓棧，將常量200壓棧，調用foo2，創建棧幀。foo3函數壓棧，變量c引用壓棧，調用foo3函數，創建棧幀，foo3中內建函數中查找print壓棧，將字符常量和變量d壓棧。foo3完成print函數調用后返回。foo2恢復調用，執行print后，返回值，main中foo2調用結束后彈出棧頂，main繼續執行print函數調用，彈出棧頂，main函數返回
   

 函數中壓棧,執行流程。

遞歸Recursion

1. 函數直接或者間接調用自身就是遞歸
2. 遞歸需要有邊界條件、遞歸前進段，遞歸返回段
3. 遞歸一定需要有邊界條件
4. 當邊界條件不滿足的時候，遞進前進
5. 當邊界條件滿足的時候，遞歸返回
   

 遞歸要求

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

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

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

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

遞歸的性能

循環稍微復雜一些，但是只要不是死循環，可以多次迭代直至算出結果
遞歸還有深度限制，如果遞歸復雜，函數反復壓棧，棧內存很快會溢出

間接遞歸

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

間接遞歸，是通過別的函數調用了函數自身，但是如果構成了循環遞歸調用是非常危險的，但是往往這種情況在代碼復雜的情況下，還是有可能發生這種調用的，要用代碼的規范來避免這種遞歸調用的發生

遞歸總結

1. 遞歸是一種很自然的表達，符合邏輯思維
2. 遞歸相對運行效率低，每一次調用函數都要開辟新的棧幀
3. 遞歸有深度限制，如果遞歸層次太深，函數反復壓棧，棧內存很快就溢出了
4. 如果是有限次數的遞歸，可以使用遞歸調用，或者使用循環代替，循環代碼稍微復雜一些，但是只要不是死循環，過次迭代直至算出結果
5. 絕大多數遞歸，都可以使用循環實現
6. 即使遞歸代碼很簡潔，能不用盡量不使用遞歸
   

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