|
在函數(shù)內(nèi)部，可以調(diào)用其他函數(shù)。如果一個函數(shù)在內(nèi)部調(diào)用自身本身，這個函數(shù)就是遞歸函數(shù) 計算階乘n! = 1 x 2 x 3 x ... x n def fact(n): if n==1: return 1 return n * fact(n - 1) 遞歸函數(shù)的優(yōu)點是定義簡單，邏輯清晰。理論上，所有的遞歸函數(shù)都可以寫成循環(huán)的方式， 但循環(huán)的邏輯不如遞歸清晰。 使用遞歸函數(shù)需要注意防止棧溢出。在計算機中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的， 每當(dāng)進(jìn)入一個函數(shù)調(diào)用，棧就會加一層棧幀，每當(dāng)函數(shù)返回，棧就會減一層棧幀。 由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多，會導(dǎo)致棧溢出。可以試試fact(1000)：報錯 解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化，事實上尾遞歸和循環(huán)的效果是一樣的，所以，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。 尾遞歸是指，在函數(shù)返回的時候，調(diào)用自身本身，并且，return語句不能包含表達(dá)式。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無論調(diào)用多少次，都只占用一個棧幀，不會出現(xiàn)棧溢出的情況。 上面的fact(n)函數(shù)由于return n * fact(n - 1)引入了乘法表達(dá)式，所以就不是尾遞歸了。要改成尾遞歸方式，需要多一點代碼，主要是要把每一步的乘積傳入到遞歸函數(shù)中： 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) 可以看到，return fact_iter(num - 1, num * product)僅返回遞歸函數(shù)本身，num - 1和num * product在函數(shù)調(diào)用前就會被計算，不影響函數(shù)調(diào)用。 fact(5)對應(yīng)的fact_iter(5, 1)的調(diào)用如下： ===> fact_iter(5, 1) ===> fact_iter(4, 5) ===> fact_iter(3, 20) ===> fact_iter(2, 60) ===> fact_iter(1, 120) ===> 120 尾遞歸調(diào)用時，如果做了優(yōu)化，棧不會增長，因此，無論多少次調(diào)用也不會導(dǎo)致棧溢出。 遺憾的是，大多數(shù)編程語言沒有針對尾遞歸做優(yōu)化，Python解釋器也沒有做優(yōu)化，所以，即使把上面的fact(n)函數(shù)改成尾遞歸方式，也會導(dǎo)致棧溢出 # 利用遞歸函數(shù)移動漢諾塔: def move(n, a, b, c): if n == 1: print('move', a, '-->', c) else: move(n-1, a, c, b) move(1, a, b, c) move(n-1, b, a, c) move(4, 'A', 'B', 'C') 分享知識，分享快樂！希望中國站在編程之巔！
360圖書館館號：rsgz002.360doc.com |
|
|
