遞歸的基本概念網(wǎng)上一大堆斋陪，這里說(shuō)一下個(gè)人認(rèn)為重要的點(diǎn)。
（3.1）基本條件和遞歸條件
編寫遞歸函數(shù)時(shí)置吓，必須告訴它何時(shí)停止遞歸无虚。正因?yàn)槿绱耍總€(gè)遞歸函數(shù)都有兩部分:基線 條件(base case)和遞歸條件(recursive case)衍锚。遞歸條件指的是函數(shù)調(diào)用自己友题，而基線條件則 指的是函數(shù)不再調(diào)用自己，從而避免形成無(wú)限循環(huán)戴质。
（3.2）棧
這里提一下一個(gè)概念：調(diào)用棧（call stack）
假設(shè)你去野外燒烤度宦，并為此創(chuàng)建了一個(gè)待辦事項(xiàng)清單——一疊 便條。
之前討論數(shù)組和鏈表時(shí)告匠，也有一個(gè)待辦事項(xiàng)清單戈抄。你可將待辦事 項(xiàng)添加到該清單的任何地方，還可刪除任何一個(gè)待辦事項(xiàng)后专。一疊便條要簡(jiǎn) 單得多:插入的待辦事項(xiàng)放在清單的最前面;讀取待辦事項(xiàng)時(shí)划鸽，你只讀取 最上面的那個(gè)，并將其刪除戚哎。因此這個(gè)待辦事項(xiàng)清單只有兩種操作:壓入(插入)和彈出(刪除并讀取)裸诽。
下面來(lái)看看如何使用這個(gè)待辦事項(xiàng)清單。
這種數(shù)據(jù)結(jié)構(gòu)稱為棧建瘫。棧是一種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)崭捍，剛才我們一直在使用它，卻沒(méi)有意識(shí)到!
（3.2.1）調(diào)用棧
計(jì)算機(jī)內(nèi)部使用的棧 我們稱為 調(diào)用棧啰脚。通過(guò)一個(gè)簡(jiǎn)單的函數(shù)了解一下殷蛇；
def greet(name):
print "hello, " + name + "!" greet2(name)
print "getting ready to say bye..."
bye()
這個(gè)函數(shù)問(wèn)候用戶实夹，再調(diào)用另外兩個(gè)函數(shù)。這兩個(gè)函數(shù)的代碼如下:
def greet2(name):
print "how are you, " + name + "?"
def bye():
print "ok bye!"
下面詳細(xì)介紹調(diào)用函數(shù)時(shí)發(fā)生的情況粒梦。
假設(shè)你調(diào)用greet("maggie")亮航，計(jì)算機(jī)將首先為該函數(shù)調(diào)用分配一塊內(nèi)存。
我們來(lái)使用這些內(nèi)存匀们。變量name被設(shè)置為maggie缴淋，這需要存儲(chǔ)到內(nèi)存中。
每當(dāng)你調(diào)用函數(shù)時(shí)泄朴，計(jì)算機(jī)都像這樣將函數(shù)調(diào)用涉及的
所有變量的值存儲(chǔ)到內(nèi)存中重抖。接下來(lái)， 你打印hello, maggie!祖灰，再調(diào)用greet2("maggie")钟沛。同樣，計(jì)算機(jī)也為這個(gè)函數(shù)調(diào)用分配一 塊內(nèi)存局扶。
計(jì)算機(jī)使用一個(gè)棧來(lái)表示這些內(nèi)存塊恨统，其中第二個(gè)內(nèi)存塊位于第一個(gè)內(nèi)存塊上面
然后從函數(shù)調(diào)用返回。此時(shí)三妈，棧頂?shù)膬?nèi)存塊被彈出畜埋。
現(xiàn)在，棧頂?shù)膬?nèi)存塊是函數(shù)greet的畴蒲，這意味著你返回到了函數(shù)greet悠鞍。當(dāng)你調(diào)用函數(shù)greet2 時(shí)，函數(shù)greet只執(zhí)行了一部分
如果在當(dāng)前函數(shù)里調(diào)用另外一個(gè)函數(shù)饿凛，當(dāng)前函數(shù)暫停并處于未完成狀態(tài)狞玛，該函數(shù)的所有變量都還在內(nèi)存中。
你回到函數(shù) greet涧窒，并從離開(kāi)的地方開(kāi)始接著往下執(zhí)行，再調(diào)用 函數(shù)bye锭亏。
函數(shù)bye 返回之后：
現(xiàn)在你又回到了函數(shù)greet纠吴。由于沒(méi)有別的事情要做，你就從函數(shù)greet返回慧瘤。這個(gè)棧用于存儲(chǔ)多個(gè)函數(shù)的變量戴已，被稱為調(diào)用棧。
（3.3）遞歸調(diào)用棧
遞歸函數(shù)也使用調(diào)用棧! 下面舉例說(shuō)明：聲明一個(gè)階乘函數(shù)锅减，詳細(xì)分析一下 調(diào)用棧
函數(shù)：
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
當(dāng)首次調(diào)用為fact(3)的時(shí)候糖儡，調(diào)用棧的變化如下：
注意，每個(gè)fact調(diào)用都有自己的x變量怔匣。在一個(gè)函數(shù)調(diào)用中不能訪問(wèn)另一個(gè)的x變量握联。
使用棧雖然很方便，但是也要付出代價(jià):存儲(chǔ)詳盡的信息可能占用大量的內(nèi)存。每個(gè)函數(shù)調(diào) 用都要占用一定的內(nèi)存金闽，如果棧很高纯露，就意味著計(jì)算機(jī)存儲(chǔ)了大量函數(shù)調(diào)用的信息。在這種情況 下代芜，你有兩種選擇埠褪。
- 重新編寫代碼，轉(zhuǎn)而使用
循環(huán)挤庇。 - 使用
尾遞歸钞速。
小結(jié)：
- 遞歸指的是調(diào)用自己的函數(shù)。
- 每個(gè)遞歸函數(shù)都有兩個(gè)條件:
基線條件和遞歸條件嫡秕。 - 棧有兩種操作:
壓入和彈出渴语。 - 所有函數(shù)調(diào)用都進(jìn)入調(diào)用棧。
- 調(diào)用椞云校可能很長(zhǎng)遵班，這將占用大量的內(nèi)存。
