12函數執行過程_遞歸函數

?

目錄

函數執行流程：... 1

recursion：... 3

?

?

?

recursion，遞歸函數

?

函數執行流程：

http://pythontutor.com/visualize.html#mode=edit

?

例：

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

???

main()

執行過程：

全局幀中生成foo1,foo2,foo3,main函數對象；

main函數調用；

main中查找內建函數print壓棧，將常量字符串（main called）壓棧，調用函數print，彈出棧頂；

main中全局查找函數foo1壓棧，將常量100,101壓棧，調用函數foo1，創建棧幀；print函數壓棧，字符串和變量b,b1壓棧，調用函數，彈出棧頂，返回值；

main中全局查找函數foo2壓棧，將常量200壓棧，調用函數foo2，創建棧幀；foo3函數壓棧，變量c引用壓棧，調用foo3，創建棧幀，foo3完成，print函數調用后返回；foo2恢復調用，執行print后返回值；

main中foo2調用結束，彈出棧頂；main繼續執行，print函數調用，彈出棧頂，main函數返回；

?

注：

棧，后進先出；

保護當前函數運行的數據，出現函數調用，依次壓棧；

保護現場-->函數壓棧-->給函數創建空間frame-->在frame內執行-->依次出棧-->恢復現場；

?

?

?

recursion：

函數直接或者間接調用自身就是遞歸；

遞歸需要有邊界條件、遞歸前進段（壓棧）、遞歸返回段（彈出）；

遞歸一定要有邊界條件（沒有邊界條件自己調自己會棧溢出、內存溢出，會將計算機資源耗盡，無限調用）；

當邊界條件不滿足時，遞歸前進；

當邊界條件滿足時，遞歸返回；

直接遞歸，自己調自己；

間接遞歸，通過別的函數調用了函數自身；

?

recursion要求：

一定要有退出條件，遞歸調用一定要執行到這個退出條件，沒有退出條件的遞歸調用，就是無限調用；

遞歸調用的深度不宜過深，python對遞歸調用的深度作了限制，以保護解釋器；超過遞歸深度限制，拋RecursionError: maximum recursion depth excedded超出最大深度；sys.getrecursionlimit()，總共不能超過1000層，自己可用980多，還有其它函數在用；sys.setrecursionlimit(2000)，不要改此項，生產中函數復雜，變量、常量各種對象都用內存；

?

recursion的性能：

循環稍微復雜一些，但只要不是死循環，可以多次迭代直至算出結果；

fib函數代碼極簡易懂，但只能獲取到最外層的函數調用，內部遞歸結果都是中間結果，且給定一個n都要進行近2n次遞歸，深度越深效率越低，為了獲取fibnacci需要外面再套一個n次的for循環，效率就更低了；

遞歸還有深度限制，如果遞歸復雜，函數反復壓棧，堆內存很快就溢出了；

?

recursion總結：

遞歸是一種很自然的表達，符合邏輯思維；

遞歸相對運行效率低，每一次調用函數都要開辟棧幀；

遞歸有深度限制，如果遞歸層次太深，函數反復壓棧，棧內存很快就溢出了；

如果是有限次數的遞歸，可以使用遞歸調用，或者使用循環代替，循環的代碼稍復雜些，但只要不是死循環，可以多次迭代，直至算出結果；

絕大多數遞歸，都可使用循環實現；

即使遞歸代碼很簡潔，但能不用則不用；

?

fibnacci number

如果設F(n)為該數列的第n項，n∈N*，即F(n)=F(n-1)+F(n-2)；

F(0)=0

F(1)=1

F(n)=F(n-1)+F(n-2)

?

例：

import datetime
import sys

 start = datetime.datetime.now()
 pre = 0
cur = 1
print(pre,cur,end=' ')
 n = 35

for _ in range(n-1):
 ??? pre,cur = cur,pre+cur
 ??? print(cur,end=' ')
print()

 delta = (datetime.datetime.now() - start).total_seconds()
print(delta)

print(sys.getrecursionlimit())

?

例：

import datetime

 start = datetime.datetime.now()
def fib(n):
 ??? return 1 if n < 2 else fib(n-1) + fib(n-2)

for i in range(35):
 ??? print(fib(i),end=' ')
print()

 delta = (datetime.datetime.now() - start).total_seconds()
print(delta)

注：

代碼雖很精簡，但效率低，經測耗時8.127465s；

?

例：

def fib(n,pre=0,cur=1):
 ??? pre,cur = cur,pre+cur
 ??? print(cur,end=' ')
 ??? if n == 2:
 ??????? return
 ??? fib(n-1,pre,cur)

 fib(10)

注：

改進，與循環思想類似；

參數n是邊界條件，用n來計數；

上一次的計算結果，直接作為函數的實參；

效率很高；

和循環比較，性能相近，所以遞歸并不一定效率低下，但遞歸有深度限制；

?

間接遞歸：

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

def foo1():

??? foo2()

def foo2():

??? foo1()

foo1()

?

習題：

1、求n的階乘？

2、將一個數逆序放入列表中，1234-->[4,3,2,1]？

3、解決猴子吃桃問題？

?

1、

方一：

def fac(n):
 ??? return 1 if n == 1 else n * fac(n-1)

print(fac(5))

方二：

def fac(num,mul=1):
 ??? mul *= num
 ??? if num == 1:
 ??????? return mul
 ??? return fac(num-1,mul)

print(fac(5))

################

def fac(num,mul=None):
 ??? if mul is None:
 ??????? mul = [1]
 ??? if num == 1:
 ??????? return mul[0]
 ??? mul[0] *= num
 ??? fac(num-1,mul)
 ??? return mul

print(fac(5))

################

def fac(num,mul=1):
 ??? if num == 1:
 ??????? return mul
 ??? mul *= num
 ??? print(mul)
 ??? fac(num-1,mul)
 ??? return mul

 fac(5)

?

2、

方一：

def rev(num,lst=None):
 ??? if lst is None:
 ??????? lst = []
 ??? x,y = divmod(num,10)
 ??? lst.append(y)
 ??? if x == 0:
 ??????? return lst
 ??? return rev(x,lst)

print(rev(1234))

方二：

def rev(num,target=[]):
 ??? if num:
 ??????? target.append(num[len(num)-1])?? #等價于target.append(num[-1:]
 ??????? rev(num[:len(num)-1])
 ??? return target

print(rev(str(1234)))

注：

target是位置參數，只不過有默認值；rev(num,*,target),這個target是關鍵字參數且是keyword-only參數；位置參數的默認值放在__defaults__里，關鍵字參數的默認值在__kwdefaults__里；

函數對象沒變，每次都是rev這個對象，所以該對象的默認值是固定的；

方三：

num = str(1234)

def rev(x):
 ??? if x == -1:
 ??????? return ''
 ??? return num[x] + rev(x-1)

print(rev(len(num)-1))

?

3、

def peach(days=10):
 ??? if days == 1:
 ??????? return 1
 ??? return (peach(days-1)+1) * 2

print(peach())

注：

這里必須是10，因為return?(peach(days-1)+1)*2立即拿不到結果，必須通過再次進入函數時，判斷是不是到了最后一天；即，當前使用的值是由下一次函數調用得到，所以要執行10次函數調用；

###############

def peach(days=1):?? #days只用于計數
 ??? if days == 10:
 ??????? return 1
 ??? return (peach(days+1)+1) * 2

print(peach())

?

?