本文是廖雪峰教程的筆記。
- 在函數(shù)內(nèi)部览祖，可以調(diào)用其他函數(shù)。如果一個函數(shù)在內(nèi)部調(diào)用自身本身炊琉，這個函數(shù)就是遞歸函數(shù)展蒂。例如計算階乘的函數(shù)：
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)致棧溢出目锭。
- 解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化，事實上尾遞歸和循環(huán)的效果是一樣的纷捞，所以痢虹，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。
- 尾遞歸是指主儡，在函數(shù)返回的時候奖唯，調(diào)用自身本身，并且糜值，return語句不能包含表達(dá)式丰捷。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化寂汇，使遞歸本身無論調(diào)用多少次病往，都只占用一個棧幀，不會出現(xiàn)棧溢出的情況骄瓣。例如上述階乘函數(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)
遺憾的是停巷，大多數(shù)編程語言沒有針對尾遞歸做優(yōu)化，Python解釋器也沒有做優(yōu)化榕栏，所以叠穆，即使把上面的fact(n)函數(shù)改成尾遞歸方式，也會導(dǎo)致棧溢出臼膏。
小結(jié)
- 使用遞歸函數(shù)的優(yōu)點是邏輯簡單清晰，缺點是過深的調(diào)用會導(dǎo)致棧溢出示损。
- 針對尾遞歸優(yōu)化的語言可以通過尾遞歸防止棧溢出渗磅。尾遞歸事實上和循環(huán)是等價的，沒有循環(huán)語句的編程語言只能通過尾遞歸實現(xiàn)循環(huán)检访。
- Python標(biāo)準(zhǔn)的解釋器沒有針對尾遞歸做優(yōu)化始鱼，任何遞歸函數(shù)都存在棧溢出的問題。
