計(jì)算機(jī)科學(xué)的新學(xué)生通常難以理解遞歸程序設(shè)計(jì)的概念院崇。遞歸思想之所以困難，原因在于它非常像是循環(huán)推理（circular reasoning）袍祖。它也不是一個(gè)直觀的過(guò)程底瓣；當(dāng)我們指揮別人做事的時(shí)候，我們極少會(huì)遞歸地指揮他們盲泛。
Introduction
遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法濒持。
遞歸算法的實(shí)質(zhì)是把問(wèn)題分解成規(guī)模縮小的同類(lèi)問(wèn)題的子問(wèn)題寺滚，然后遞歸調(diào)用方法來(lái)表示問(wèn)題的解柑营。遞歸算法對(duì)解決一大類(lèi)問(wèn)題很有效，它可以使算法簡(jiǎn)潔和易于理解村视。
遞歸算法官套，其實(shí)說(shuō)白了，就是程序的自身調(diào)用。它表現(xiàn)在一段程序中往往會(huì)遇到調(diào)用自身的那樣一種coding策略奶赔，這樣我們就可以利用大道至簡(jiǎn)的思想惋嚎，把一個(gè)大的復(fù)雜的問(wèn)題層層轉(zhuǎn)換為一個(gè)小的和原問(wèn)題相似的問(wèn)題來(lái)求解的這樣一種策略。
遞歸往往能給我們帶來(lái)非常簡(jiǎn)潔非常直觀的代碼形勢(shì)站刑，從而使我們的編碼大大簡(jiǎn)化另伍，然而遞歸的思維確實(shí)跟我們的常規(guī)思維相逆的，我們通常都是從上而下的思維問(wèn)題绞旅， 而遞歸趨勢(shì)從下往上的進(jìn)行思維摆尝。這樣我們就能看到我們會(huì)用很少的語(yǔ)句解決了非常大的問(wèn)題，所以遞歸策略的最主要體現(xiàn)就是小的代碼量解決了非常復(fù)雜的問(wèn)題因悲。
遞歸算法解決問(wèn)題的特點(diǎn)：
? 遞歸就是方法里調(diào)用自身堕汞。
? 在使用遞增歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件晃琳，稱(chēng)為遞歸出口讯检。
? 遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低卫旱。所以一般不提倡用遞歸算法設(shè)計(jì)程序人灼。
? 在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)誊涯。遞歸次數(shù)過(guò)多容易造成棧溢出等挡毅，所以一般不提倡用遞歸算法設(shè)計(jì)程序蒜撮。
遞歸算法要求暴构。遞歸算法所體現(xiàn)的“重復(fù)”一般有三個(gè)要求：
(1) 是每次調(diào)用在規(guī)模上都有所縮小（通常是減半）段磨；
(2) 是相鄰兩次重復(fù)之間有緊密的聯(lián)系取逾，前一次要為后一次做準(zhǔn)備（通常前一次的輸出就作為后一次的輸入）；
(3) 是在問(wèn)題的規(guī)模極小時(shí)必須用直接給出解答而不再進(jìn)行遞歸調(diào)用苹支，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達(dá)到直接解答的大小為條件)砾隅，無(wú)條件遞歸調(diào)用將會(huì)成為死循環(huán)而不能正常結(jié)束。
從遞歸的經(jīng)典示例開(kāi)始
計(jì)算階乘
計(jì)算階乘是遞歸程序設(shè)計(jì)的一個(gè)經(jīng)典示例债蜜。計(jì)算某個(gè)數(shù)的階乘就是用那個(gè)數(shù)去乘包括 1 在內(nèi)的所有比它小的數(shù)晴埂。例如，factorial(5) 等價(jià)于 5*4*3*2*1寻定，而 factorial(3) 等價(jià)于 3*2*1儒洛。
階乘的一個(gè)有趣特性是，某個(gè)數(shù)的階乘等于起始數(shù)（starting number）乘以比它小1的數(shù)的階乘狼速。例如琅锻，factorial(5) 與5 * factorial(4) 相同。您很可能會(huì)像這樣編寫(xiě)階乘函數(shù)：
(注：本文的程序示例用C語(yǔ)言編寫(xiě))
不過(guò)，這個(gè)函數(shù)的問(wèn)題是恼蓬，它會(huì)永遠(yuǎn)運(yùn)行下去惊完，因?yàn)樗鼪](méi)有終止的地方。函數(shù)會(huì)連續(xù)不斷地調(diào)用 factorial处硬。 當(dāng)計(jì)算到零時(shí)小槐，沒(méi)有條件來(lái)停止它，所以它會(huì)繼續(xù)調(diào)用零和負(fù)數(shù)的階乘荷辕。因此本股，我們的函數(shù)需要一個(gè)條件，告訴它何時(shí)停止桐腌。
由于小于 1 的數(shù)的階乘沒(méi)有任何意義拄显，所以我們?cè)谟?jì)算到數(shù)字 1 的時(shí)候停止，并返回 1 的階乘（即 1）案站。因此躬审，真正的遞歸函數(shù)類(lèi)似于：
精密詳解c/c++遞歸算法，感受遞歸算法的獨(dú)特用處
可見(jiàn)蟆盐，只要初始值大于零承边，這個(gè)函數(shù)就能夠終止。停止的位置稱(chēng)為 基線條件（base case）石挂〔┲基線條件是遞歸程序的最底層位置，在此位置時(shí)沒(méi)有必要再進(jìn)行操作痹愚，可以直接返回一個(gè)結(jié)果富岳。所有遞歸程序都必須至少擁有一個(gè)基線條件，而且 必須確保它們最終會(huì)達(dá)到某個(gè)基線條件拯腮；否則窖式，程序?qū)⒂肋h(yuǎn)運(yùn)行下去，直到程序缺少內(nèi)存或者椂溃空間萝喘。
斐波納契數(shù)列
斐波納契數(shù)列(Fibonacci Sequence)，最開(kāi)始用于描述兔子生長(zhǎng)的數(shù)目時(shí)用上了這數(shù)列琼懊。從數(shù)學(xué)上阁簸，費(fèi)波那契數(shù)列是以遞歸的方法來(lái)定義：
這樣斐波納契數(shù)列的遞歸程序就可以非常清晰的寫(xiě)出來(lái)了：
精密詳解c/c++遞歸算法，感受遞歸算法的獨(dú)特用處
遞歸程序的基本步驟
每一個(gè)遞歸程序都遵循相同的基本步驟：
(1) 初始化算法哼丈。遞歸程序通常需要一個(gè)開(kāi)始時(shí)使用的種子值（seed value）启妹。要完成此任務(wù)，可以向函數(shù)傳遞參數(shù)削祈，或者提供一個(gè)入口函數(shù)翅溺， 這個(gè)函數(shù)是非遞歸的脑漫，但可以為遞歸計(jì)算設(shè)置種子值。
(2) 檢查要處理的當(dāng)前值是否已經(jīng)與基線條件相匹配咙崎。如果匹配优幸，則進(jìn)行處理并返回值。
(3) 使用更小的或更簡(jiǎn)單的子問(wèn)題（或多個(gè)子問(wèn)題）來(lái)重新定義答案褪猛。
(4) 對(duì)子問(wèn)題運(yùn)行算法网杆。
(5) 將結(jié)果合并入答案的表達(dá)式。
(6) 返回結(jié)果伊滋。
使用歸納定義
有時(shí)候碳却，編寫(xiě)遞歸程序時(shí)難以獲得更簡(jiǎn)單的子問(wèn)題。不過(guò)笑旺，使用歸納定義的（inductively-defined）數(shù)據(jù)集 可以令子問(wèn)題的獲得更為簡(jiǎn)單昼浦。歸納定義的數(shù)據(jù)集是根據(jù)自身定義的數(shù)據(jù)結(jié)構(gòu) —— 這叫做歸納定義（inductive definition）。
例如筒主，鏈表就是根據(jù)其本身定義出來(lái)的关噪。鏈表所包含的節(jié)點(diǎn)結(jié)構(gòu)體由兩部分構(gòu)成：它所持有的數(shù)據(jù)，以及指向另一個(gè)節(jié)點(diǎn)結(jié)構(gòu)體（或者是 NULL乌妙，結(jié)束鏈表）的指針使兔。 由于節(jié)點(diǎn)結(jié)構(gòu)體內(nèi)部包含有一個(gè)指向節(jié)點(diǎn)結(jié)構(gòu)體的指針，所以稱(chēng)之為是歸納定義的藤韵。
使用歸納數(shù)據(jù)編寫(xiě)遞歸過(guò)程非常簡(jiǎn)單虐沥。注意，與我們的遞歸程序非常類(lèi)似泽艘，鏈表的定義也包括一個(gè)基線條件 —— 在這里是 NULL 指針欲险。 由于 NULL 指針會(huì)結(jié)束一個(gè)鏈表，所以我們也可以使用 NULL 指針條件作為基于鏈表的很多遞歸程序的基線條件悉盆。
下面看兩個(gè)例子盯荤。
鏈表求和示例
讓我們來(lái)看一些基于鏈表的遞歸函數(shù)示例。假定我們有一個(gè)數(shù)字列表焕盟，并且要將它們加起來(lái)。履行遞歸過(guò)程序列的每一個(gè)步驟宏粤，以確定它如何應(yīng)用于我們的求和函數(shù)：
(1) 初始化算法脚翘。這個(gè)算法的種子值是要處理的第一個(gè)節(jié)點(diǎn)，將它作為參數(shù)傳遞給函數(shù)绍哎。
(2) 檢查基線條件来农。程序需要檢查確認(rèn)當(dāng)前節(jié)點(diǎn)是否為 NULL 列表。如果是崇堰，則返回零沃于，因?yàn)橐粋€(gè)空列表的所有成員的和為零涩咖。
(3) 使用更簡(jiǎn)單的子問(wèn)題重新定義答案。我們可以將答案定義為當(dāng)前節(jié)點(diǎn)的內(nèi)容加上列表中其余部分的和繁莹。為了確定列表其余部分的和檩互， 我們針對(duì)下一個(gè)節(jié)點(diǎn)來(lái)調(diào)用這個(gè)函數(shù)。
(4) 合并結(jié)果。遞歸調(diào)用之后，我們將當(dāng)前節(jié)點(diǎn)的值加到遞歸調(diào)用的結(jié)果上父款。
這樣我們就可以很簡(jiǎn)單的寫(xiě)出鏈表求和的遞歸程序厢塘，實(shí)例如下：
精密詳解c/c++遞歸算法，感受遞歸算法的獨(dú)特用處
漢諾塔問(wèn)題
漢諾塔（Hanoi Tower）問(wèn)題也是一個(gè)經(jīng)典的遞歸問(wèn)題幼衰，該問(wèn)題描述如下：
漢諾塔問(wèn)題：古代有一個(gè)梵塔，塔內(nèi)有三個(gè)座A、B循诉、C，A座上有64個(gè)盤(pán)子撇他，盤(pán)子大小不等打洼，大的在下，小的在上（如圖）逆粹。有一個(gè)和尚想把這64個(gè)盤(pán)子從A座移到B座募疮，但每次只能允許移動(dòng)一個(gè)盤(pán)子，并且在移動(dòng)過(guò)程中僻弹，3個(gè)座上的盤(pán)子始終保持大盤(pán)在下阿浓，小盤(pán)在上。
精密詳解c/c++遞歸算法蹋绽，感受遞歸算法的獨(dú)特用處
Hanoi Tower Solving
? 如果只有 1 個(gè)盤(pán)子芭毙，則不需要利用B塔，直接將盤(pán)子從A移動(dòng)到C卸耘。
? 如果有 2 個(gè)盤(pán)子退敦，可以先將盤(pán)子1上的盤(pán)子2移動(dòng)到B；將盤(pán)子1移動(dòng)到C蚣抗；將盤(pán)子2移動(dòng)到C侈百。這說(shuō)明了：可以借助B將2個(gè)盤(pán)子從A移動(dòng)到C，當(dāng)然翰铡，也可以借助C將2個(gè)盤(pán)子從A移動(dòng)到B钝域。
? 如果有3個(gè)盤(pán)子，那么根據(jù)2個(gè)盤(pán)子的結(jié)論锭魔，可以借助c將盤(pán)子1上的兩個(gè)盤(pán)子從A移動(dòng)到B例证；將盤(pán)子1從A移動(dòng)到C，A變成空座迷捧；借助A座织咧，將B上的兩個(gè)盤(pán)子移動(dòng)到C胀葱。
以此類(lèi)推，上述的思路可以一直擴(kuò)展到 n 個(gè)盤(pán)子的情況笙蒙，將將較小的 n-1個(gè)盤(pán)子看做一個(gè)整體抵屿，也就是我們要求的子問(wèn)題，以借助B塔為例手趣，可以借助空塔B將盤(pán)子A上面的 n-1 個(gè)盤(pán)子從A移動(dòng)到B晌该；將A最大的盤(pán)子移動(dòng)到C，A變成空塔绿渣；借助空塔A朝群，將B塔上的 n-2 個(gè)盤(pán)子移動(dòng)到A，將C最大的盤(pán)子移動(dòng)到C中符，B變成空塔…
根據(jù)以上的分析姜胖，不難寫(xiě)出程序：
精密詳解c/c++遞歸算法，感受遞歸算法的獨(dú)特用處
將循環(huán)轉(zhuǎn)化為遞歸
在下表中了解循環(huán)的特性淀散，看它們可以如何與遞歸函數(shù)的特性相對(duì)比右莱。
精密詳解c/c++遞歸算法，感受遞歸算法的獨(dú)特用處
可見(jiàn)档插，遞歸函數(shù)與循環(huán)有很多類(lèi)似之處慢蜓。實(shí)際上，可以認(rèn)為循環(huán)和遞歸函數(shù)是能夠相互轉(zhuǎn)換的郭膛。 區(qū)別在于晨抡，使用遞歸函數(shù)極少被迫修改任何一個(gè)變量 —— 只需要將新值作為參數(shù)傳遞給下一次函數(shù)調(diào)用。 這就使得您可以獲得避免使用可更新變量的所有益處则剃，同時(shí)能夠進(jìn)行重復(fù)的耘柱、有狀態(tài)的行為。
下面還是以階乘為例子棍现，循環(huán)寫(xiě)法為：
精密詳解c/c++遞歸算法调煎，感受遞歸算法的獨(dú)特用處
遞歸寫(xiě)法在第二節(jié)中已經(jīng)介紹過(guò)了，這里就不重復(fù)了己肮，可以比較一下士袄。
尾遞歸介紹
對(duì)于遞歸函數(shù)的使用，人們所關(guān)心的一個(gè)問(wèn)題是椘臃危空間的增長(zhǎng)窖剑。確實(shí)，隨著被調(diào)用次數(shù)的增加戈稿，某些種類(lèi)的遞歸函數(shù)會(huì)線性地增加棧空間的使用 —— 不過(guò)讶舰，有一類(lèi)函數(shù)鞍盗，即尾部遞歸函數(shù)需了，不管遞歸有多深，棧的大小都保持不變般甲。尾遞歸屬于線性遞歸肋乍，更準(zhǔn)確的說(shuō)是線性遞歸的子集。
函數(shù)所做的最后一件事情是一個(gè)函數(shù)調(diào)用（遞歸的或者非遞歸的）敷存，這被稱(chēng)為 尾部調(diào)用（tail-call）墓造。使用尾部調(diào)用的遞歸稱(chēng)為 尾部遞歸。當(dāng)編譯器檢測(cè)到一個(gè)函數(shù)調(diào)用是尾遞歸的時(shí)候锚烦，它就覆蓋當(dāng)前的活動(dòng)記錄而不是在棧中去創(chuàng)建一個(gè)新的觅闽。編譯器可以做到這點(diǎn)，因?yàn)檫f歸調(diào)用是當(dāng)前活躍期內(nèi)最后一條待執(zhí)行的語(yǔ)句涮俄，于是當(dāng)這個(gè)調(diào)用返回時(shí)棧幀中并沒(méi)有其他事情可做蛉拙，因此也就沒(méi)有保存棧幀的必要了。通過(guò)覆蓋當(dāng)前的棧幀而不是在其之上重新添加一個(gè)彻亲，這樣所使用的椩谐空間就大大縮減了，這使得實(shí)際的運(yùn)行效率會(huì)變得更高苞尝。
讓我們來(lái)看一些尾部調(diào)用和非尾部調(diào)用函數(shù)示例畸肆，以了解尾部調(diào)用的含義到底是什么：
精密詳解c/c++遞歸算法，感受遞歸算法的獨(dú)特用處
可見(jiàn)宙址，要使調(diào)用成為真正的尾部調(diào)用轴脐，在尾部調(diào)用函數(shù)返回之前，對(duì)其結(jié)果 不能執(zhí)行任何其他操作曼氛。
注意豁辉，由于在函數(shù)中不再做任何事情，那個(gè)函數(shù)的實(shí)際的棧結(jié)構(gòu)也就不需要了舀患。惟一的問(wèn)題是徽级，很多程序設(shè)計(jì)語(yǔ)言和編譯器不知道如何除去沒(méi)有用的棧結(jié)構(gòu)。如果我們能找到一個(gè)除去這些不需要的棧結(jié)構(gòu)的方法聊浅，那么我們的尾部遞歸函數(shù)就可以在固定大小的棧中運(yùn)行餐抢。
在尾部調(diào)用之后除去棧結(jié)構(gòu)的方法稱(chēng)為 尾部調(diào)用優(yōu)化 。
那么這種優(yōu)化是什么低匙？我們可以通過(guò)詢(xún)問(wèn)其他問(wèn)題來(lái)回答那個(gè)問(wèn)題：
(1) 函數(shù)在尾部被調(diào)用之后旷痕，還需要使用哪個(gè)本地變量？哪個(gè)也不需要顽冶。
(2) 會(huì)對(duì)返回的值進(jìn)行什么處理欺抗？什么處理也沒(méi)有。
(3) 傳遞到函數(shù)的哪個(gè)參數(shù)將會(huì)被使用强重？哪個(gè)都沒(méi)有绞呈。
好像一旦控制權(quán)傳遞給了尾部調(diào)用的函數(shù)贸人，棧中就再也沒(méi)有有用的內(nèi)容了。雖然還占據(jù)著空間佃声，但函數(shù)的棧結(jié)構(gòu)此時(shí)實(shí)際上已經(jīng)沒(méi)有用了艺智，因此，尾部調(diào)用優(yōu)化就是要在尾部進(jìn)行函數(shù)調(diào)用時(shí)使用下一個(gè)棧結(jié)構(gòu) 覆蓋 當(dāng)前的棧結(jié)構(gòu)圾亏，同時(shí)保持原來(lái)的返回地址十拣。
我們所做的本質(zhì)上是對(duì)棧進(jìn)行處理。再也不需要活動(dòng)記錄（activation record）志鹃，所以我們將刪掉它夭问，并將尾部調(diào)用的函數(shù)重定向返回到調(diào)用我們的函數(shù)。 這意味著我們必須手工重新編寫(xiě)棧來(lái)仿造一個(gè)返回地址弄跌，以使得尾部調(diào)用的函數(shù)能直接返回到調(diào)用它的函數(shù)甲喝。
Conclusion
遞歸是一門(mén)偉大的藝術(shù)，使得程序的正確性更容易確認(rèn)铛只，而不需要犧牲性能埠胖，但這需要程序員以一種新的眼光來(lái)研究程序設(shè)計(jì)。對(duì)新程序員來(lái)說(shuō)淳玩，命令式程序設(shè)計(jì)通常是一個(gè)更為自然和直觀的起點(diǎn)直撤，這就是為什么大部分程序設(shè)計(jì)說(shuō)明都集中關(guān)注命令式語(yǔ)言和方法的原因。 不過(guò)蜕着，隨著程序越來(lái)越復(fù)雜谋竖，遞歸程序設(shè)計(jì)能夠讓程序員以可維護(hù)且邏輯一致的方式更好地組織代碼。
