12函數(shù)執(zhí)行過程_遞歸函數(shù)

?

目錄

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

recursion：... 3

?

?

?

recursion，遞歸函數(shù)

?

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

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

執(zhí)行過程：

全局幀中生成foo1,foo2,foo3,main函數(shù)對(duì)象；

main函數(shù)調(diào)用；

main中查找內(nèi)建函數(shù)print壓棧，將常量字符串（main called）壓棧，調(diào)用函數(shù)print，彈出棧頂；

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

main中全局查找函數(shù)foo2壓棧，將常量200壓棧，調(diào)用函數(shù)foo2，創(chuàng)建棧幀；foo3函數(shù)壓棧，變量c引用壓棧，調(diào)用foo3，創(chuàng)建棧幀，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ù)返回；

?

注：

棧，后進(jìn)先出；

保護(hù)當(dāng)前函數(shù)運(yùn)行的數(shù)據(jù)，出現(xiàn)函數(shù)調(diào)用，依次壓棧；

保護(hù)現(xiàn)場(chǎng)-->函數(shù)壓棧-->給函數(shù)創(chuàng)建空間frame-->在frame內(nèi)執(zhí)行-->依次出棧-->恢復(fù)現(xiàn)場(chǎng)；

?

?

?

recursion：

函數(shù)直接或者間接調(diào)用自身就是遞歸；

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

遞歸一定要有邊界條件（沒有邊界條件自己調(diào)自己會(huì)棧溢出、內(nèi)存溢出，會(huì)將計(jì)算機(jī)資源耗盡，無限調(diào)用）；

當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；

當(dāng)邊界條件滿足時(shí)，遞歸返回；

直接遞歸，自己調(diào)自己；

間接遞歸，通過別的函數(shù)調(diào)用了函數(shù)自身；

?

recursion要求：

一定要有退出條件，遞歸調(diào)用一定要執(zhí)行到這個(gè)退出條件，沒有退出條件的遞歸調(diào)用，就是無限調(diào)用；

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

?

recursion的性能：

循環(huán)稍微復(fù)雜一些，但只要不是死循環(huán)，可以多次迭代直至算出結(jié)果；

fib函數(shù)代碼極簡(jiǎn)易懂，但只能獲取到最外層的函數(shù)調(diào)用，內(nèi)部遞歸結(jié)果都是中間結(jié)果，且給定一個(gè)n都要進(jìn)行近2n次遞歸，深度越深效率越低，為了獲取fibnacci需要外面再套一個(gè)n次的for循環(huán)，效率就更低了；

遞歸還有深度限制，如果遞歸復(fù)雜，函數(shù)反復(fù)壓棧，堆內(nèi)存很快就溢出了；

?

recursion總結(jié)：

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

遞歸相對(duì)運(yùn)行效率低，每一次調(diào)用函數(shù)都要開辟棧幀；

遞歸有深度限制，如果遞歸層次太深，函數(shù)反復(fù)壓棧，棧內(nèi)存很快就溢出了；

如果是有限次數(shù)的遞歸，可以使用遞歸調(diào)用，或者使用循環(huán)代替，循環(huán)的代碼稍復(fù)雜些，但只要不是死循環(huán)，可以多次迭代，直至算出結(jié)果；

絕大多數(shù)遞歸，都可使用循環(huán)實(shí)現(xiàn)；

即使遞歸代碼很簡(jiǎn)潔，但能不用則不用；

?

fibnacci number

如果設(shè)F(n)為該數(shù)列的第n項(xiàng)，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)

注：

代碼雖很精簡(jiǎn)，但效率低，經(jīng)測(cè)耗時(shí)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)

注：

改進(jìn)，與循環(huán)思想類似；

參數(shù)n是邊界條件，用n來計(jì)數(shù)；

上一次的計(jì)算結(jié)果，直接作為函數(shù)的實(shí)參；

效率很高；

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

?

間接遞歸：

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

def foo1():

??? foo2()

def foo2():

??? foo1()

foo1()

?

習(xí)題：

1、求n的階乘？

2、將一個(gè)數(shù)逆序放入列表中，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])?? #等價(jià)于target.append(num[-1:]
 ??????? rev(num[:len(num)-1])
 ??? return target

print(rev(str(1234)))

注：

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

函數(shù)對(duì)象沒變，每次都是rev這個(gè)對(duì)象，所以該對(duì)象的默認(rèn)值是固定的；

方三：

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，因?yàn)閞eturn?(peach(days-1)+1)*2立即拿不到結(jié)果，必須通過再次進(jìn)入函數(shù)時(shí)，判斷是不是到了最后一天；即，當(dāng)前使用的值是由下一次函數(shù)調(diào)用得到，所以要執(zhí)行10次函數(shù)調(diào)用；

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

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

print(peach())

?

?