1.遞歸

假設(shè)你在祖母(老外都喜歡舉祖母的例子)的閣樓中翻箱倒柜肥荔，發(fā)現(xiàn)了一個上鎖的神秘手提箱。

祖母告訴你朝群，鑰匙很可能在下面這個盒子里燕耿。

這個盒子里有盒子，而盒子里的盒子又有盒子姜胖。鑰匙就在某個盒子中誉帅。為找到鑰匙，你將使用什么算法右莱？

以下是一種方法：

(1) 創(chuàng)建一個要查找的盒子堆蚜锨。

(2) 從盒子堆取出一個盒子，在里面找慢蜓。

(3) 如果找到的是盒子亚再，就將其加入盒子堆中，以便以后再查找晨抡。

(4) 如果找到鑰匙氛悬，則大功告成！

(5) 回到第二步耘柱。

下面是另一種方法圆雁。

(1) 檢查盒子中的每樣東西。

(2) 如果是盒子帆谍，就回到第一步。

(3) 如果是鑰匙轴咱，就大功告成汛蝙！

在你看來烈涮，哪種方法更容易呢？

我們從直觀上來看窖剑，第二種的步驟相對來說比較少坚洽。

第一種是while循環(huán)，只要盒子堆不空西土，就從中取一個盒子讶舰，并仔細查找。

第二種是遞歸需了，自己調(diào)自己跳昼，偽代碼如下：

遞歸只是讓解決方案更清晰，并沒有性能上的優(yōu)勢肋乍。實際上鹅颊，在有些情況下，使用循環(huán)的性能更好墓造。

2.基線條件和遞歸條件

由于遞歸函數(shù)調(diào)用自己堪伍，因此編寫這樣的函數(shù)時很容易出錯，進而導致無限循環(huán)觅闽。例如帝雇，假設(shè)你要編寫一個像下面這樣倒計時的函數(shù)。

def countdown(i):

? ? ? ? ? ? print i

? ? ? ? ? ? countdown(i-1)

如果你運行上述代碼蛉拙，將發(fā)現(xiàn)一個問題：這個函數(shù)運行起來沒完沒了尸闸！

編寫遞歸函數(shù)時，必須告訴它何時停止遞歸刘离。正因為如此室叉，每個遞歸函數(shù)都有兩部分：基線條件（base case）和遞歸條件（recursive case）。遞歸條件指的是函數(shù)調(diào)用自己硫惕，而基線條件則指的是函數(shù)不再調(diào)用自己茧痕，從而避免形成無限循環(huán)。

我們來給函數(shù)countdown添加基線條件恼除。

現(xiàn)在踪旷，這個函數(shù)將像預(yù)期的那樣運行，如下所示豁辉。

3.棧

調(diào)用棧不僅對編程來說很重要令野，使用遞歸時也必須理解這個概念。

有一個待辦清單的例子徽级，你可將待辦事項添加到該清單的任何地方气破，還可刪除任何一個待辦事項。一疊便條要簡單得多：插入的待辦事項放在清單的最前面餐抢；讀取待辦事項時现使，你只讀取最上面的那個低匙，并將其刪除。因此這個待辦事項清單只有兩種操作：壓入（插入）和彈出（刪除并讀忍夹狻）顽冶。

3.1調(diào)用棧

計算機在內(nèi)部使用被稱為調(diào)用棧的棧。我們來看看計算機是如何使用調(diào)用棧的售碳。下面是一個簡單的函數(shù)强重。

? ? ? ? def greet(name):

? ? ? ? ? ? print "hello, " + name + "! "

? ? ? ? ? ? greet2(name)

? ? ? ? ? ? print "getting ready to say bye..."

? ? ? ? ? ? bye()

這個函數(shù)問候用戶，再調(diào)用另外兩個函數(shù)贸人。這兩個函數(shù)的代碼如下间景。

? ? ? ? def greet2(name):

? ? ? ? ? ? print "how are you, " + name + "? "

? ? ? ? def bye():

? ? ? ? ? ? print "ok bye! "

假設(shè)你調(diào)用greet("maggie")，計算機將首先為該函數(shù)調(diào)用分配一塊內(nèi)存灸姊。

我們來使用這些內(nèi)存拱燃。變量name被設(shè)置為maggie，這需要存儲到內(nèi)存中力惯。

每當你調(diào)用函數(shù)時碗誉，計算機都像這樣將函數(shù)調(diào)用涉及的所有變量的值存儲到內(nèi)存中。接下來父晶，你打印hello, maggie!哮缺，再調(diào)用greet2("maggie")。同樣甲喝，計算機也為這個函數(shù)調(diào)用分配一塊內(nèi)存尝苇。

計算機使用一個棧來表示這些內(nèi)存塊，其中第二個內(nèi)存塊位于第一個內(nèi)存塊上面埠胖。你打印how are you, maggie?糠溜，然后從函數(shù)調(diào)用返回。此時直撤，棧頂?shù)膬?nèi)存塊被彈出非竿。

現(xiàn)在，棧頂?shù)膬?nèi)存塊是函數(shù)greet的谋竖，這意味著你返回到了函數(shù)greet红柱。當你調(diào)用函數(shù)greet2時，函數(shù)greet只執(zhí)行了一部分蓖乘。這是本節(jié)的一個重要概念：調(diào)用另一個函數(shù)時锤悄，當前函數(shù)暫停并處于未完成狀態(tài)。該函數(shù)的所有變量的值都還在內(nèi)存中嘉抒。執(zhí)行完函數(shù)greet2后零聚，你回到函數(shù)greet，并從離開的地方開始接著往下執(zhí)行：首先打印getting ready to say bye…，再調(diào)用函數(shù)bye隶症。

在棧頂添加了函數(shù)bye的內(nèi)存塊容诬。然后，你打印ok bye!沿腰，并從這個函數(shù)返回。

現(xiàn)在你又回到了函數(shù)greet狈定。由于沒有別的事情要做颂龙，你就從函數(shù)greet返回。這個棧用于存儲多個函數(shù)的變量纽什，被稱為調(diào)用棧措嵌。

3.2 遞歸調(diào)用棧

遞歸函數(shù)也使用調(diào)用棧，我們以階乘函數(shù)為例

下面來詳細分析調(diào)用fact(3)時調(diào)用棧是如何變化的芦缰。棧頂?shù)姆娇蛑赋隽水斍皥?zhí)行到了什么地方企巢。

注意，每個fact都有自己的x變量让蕾，在一個函數(shù)的調(diào)用中不能訪問另一個x變量浪规。

使用棧雖然很方便，但是也要付出代價：存儲詳盡的信息可能占用大量的內(nèi)存探孝。每個函數(shù)調(diào)用都要占用一定的內(nèi)存笋婿，如果棧很高，就意味著計算機存儲了大量函數(shù)3調(diào)用的信息顿颅。在這種情況下缸濒，你有兩種選擇。

? 重新編寫代碼粱腻，轉(zhuǎn)而使用循環(huán)庇配。

? 使用尾遞歸。這是一個高級遞歸

4. 小結(jié)

? 遞歸指的是調(diào)用自己的函數(shù)绍些。

? 每個遞歸函數(shù)都有兩個條件：基線條件和遞歸條件捞慌。

? 棧有兩種操作：壓入和彈出。

? 所有函數(shù)調(diào)用都進入調(diào)用棧遇革。

? 調(diào)用椙淠郑可能很長，這將占用大量的內(nèi)存萝快。