?

目前創(chuàng)新互聯(lián)建站已為上千余家的企業(yè)提供了網(wǎng)站建設、域名、網(wǎng)站空間、網(wǎng)站托管、企業(yè)網(wǎng)站設計、青神網(wǎng)站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

目錄

函數(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ù)對象；

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恢復調(diào)用，執(zhí)行print后返回值；

main中foo2調(diào)用結(jié)束，彈出棧頂；main繼續(xù)執(zhí)行，print函數(shù)調(diào)用，彈出棧頂，main函數(shù)返回；

?

注：

棧，后進先出；

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

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

?

?

?

recursion：

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

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

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

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

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

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

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

?

recursion要求：

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

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

?

recursion的性能：

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

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

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

?

recursion總結(jié)：

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

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

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

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

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

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

?

fibnacci number

如果設F(n)為該數(shù)列的第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)

?

例：

importdatetime
importsys

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

for_inrange(n-1):
??? pre,cur = cur,pre+cur
???print(cur,end=' ')
print()

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

print(sys.getrecursionlimit())

?

例：

importdatetime

start = datetime.datetime.now()
deffib(n):
???return1ifn <2elsefib(n-1) + fib(n-2)

foriinrange(35):
???print(fib(i),end=' ')
print()

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

注：

代碼雖很精簡，但效率低，經(jīng)測耗時8.127465s；

?

例：

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

fib(10)

注：

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

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

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

效率很高；

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

?

間接遞歸：

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

def foo1():

??? foo2()

def foo2():

??? foo1()

foo1()

?

習題：

1、求n的階乘？

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

3、解決猴子吃桃問題？

?

1、

方一：

deffac(n):
???return1ifn ==1elsen * fac(n-1)

print(fac(5))

方二：

deffac(num,mul=1):
??? mul *= num
???ifnum ==1:
???????returnmul
???returnfac(num-1,mul)

print(fac(5))

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

deffac(num,mul=None):
???ifmulis None:
??????? mul = [1]
???ifnum ==1:
???????returnmul[0]
??? mul[0] *= num
??? fac(num-1,mul)
???returnmul

print(fac(5))

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

deffac(num,mul=1):
???ifnum ==1:
???????returnmul
??? mul *= num
???print(mul)
??? fac(num-1,mul)
???returnmul

fac(5)

?

2、

方一：

defrev(num,lst=None):
???iflstis None:
??????? lst = []
??? x,y =divmod(num,10)
??? lst.append(y)
???ifx ==0:
???????returnlst
???returnrev(x,lst)

print(rev(1234))

方二：

defrev(num,target=[]):
???ifnum:
??????? target.append(num[len(num)-1])?? #等價于target.append(num[-1:]
??????? rev(num[:len(num)-1])
???returntarget

print(rev(str(1234)))

注：

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

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

方三：

num =str(1234)

defrev(x):
???ifx == -1:
???????return''
???returnnum[x] + rev(x-1)

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

?

3、

defpeach(days=10):
???ifdays ==1:
???????return1
???return(peach(days-1)+1) *2

print(peach())

注：

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

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

defpeach(days=1):?? #days只用于計數(shù)
???ifdays ==10:
???????return1
???return(peach(days+1)+1) *2

print(peach())

?

?