學(xué)習(xí)目標(biāo)

1、掌握遞歸函數(shù)的使用。

2、理解尾遞歸優(yōu)化。

遞歸函數(shù)

在函數(shù)內(nèi)部可以調(diào)用其他函數(shù)，如果函數(shù)內(nèi)部調(diào)用自身，則這個函數(shù)就是遞歸函數(shù)。

計算階乘n!=1x2x3x...x(n-1)xn，用fact(n)表示

fact(n)=n!=1x2x3x...x(n-1)xn=(n-1)!xn=fact(n-1)xn

因此fact(n)=nxfact(n-1)

def fact(n):

? ? if n==1 :

? ? ? ? return 1

? ? return n * fact(n-1)

print(fact(5))

print(fact(100))

print(fact(1000)) #棧溢出

執(zhí)行結(jié)果

遞歸函數(shù)的優(yōu)點是定義簡單、邏輯清晰，但是使用遞歸函數(shù)需要注意防止棧溢出。解決遞歸調(diào)用棧溢出的方法是尾遞歸優(yōu)化，尾遞歸是指函數(shù)返回時調(diào)用本身且return語句不能包含表達(dá)式。

尾遞歸如果做了優(yōu)化時，棧不會增長，所以無論調(diào)多少次都不會出現(xiàn)棧溢出的問題。

上面的fact(n)函數(shù)返回return n*fact(n-1)引入了乘法表達(dá)式，就不是尾遞歸。

def fact(n) :

? ? return fact_iter(n, 1)

def fact_iter(num, product) :

? ? if num==1 :

? ? ? ? return product

? ? return fact_iter(num-1, num * product)

print(fact(5))

print(fact(100))

print(fact(1000)) #棧溢出

執(zhí)行結(jié)果

Python標(biāo)準(zhǔn)的解釋器沒有針對尾遞歸做優(yōu)化，所以任何遞歸函數(shù)都存在棧溢出的問題。