計(jì)算機(jī)系統(tǒng)概論十七章

1、第十七章第十七章遞歸遞歸17.1緒論緒論我們從描述一個(gè)你可能已經(jīng)熟悉的遞歸程序開(kāi)始這一章。假如我們想從一堆已經(jīng)按字母順序排列的試卷中查找到某個(gè)學(xué)生的成績(jī)。我們將隨機(jī)地從試卷堆的中間檢查其姓名。如果這個(gè)被隨機(jī)選中的成績(jī)不是我們想要查找的，我們將用同樣的方法查找適當(dāng)?shù)囊话?。也就是說(shuō)，取決于我們要查找的名字比試卷中間點(diǎn)的名字小或大，我們將從前一半或者后一半里重復(fù)這樣的查找。例如，假如我們要查找BabeRuth的成績(jī)，而在中間點(diǎn)，我們找到的是M

2、ickeyMantle的成績(jī)。我們將再次從初始堆中的后一半里重新查找。如果它存在于試卷堆中的話，很快地，我們將定位出BabeRuth的成績(jī)。這種查找一組已被排過(guò)序的元素的方法是遞歸的。我們?cè)谠絹?lái)越小的試卷堆中一直應(yīng)用這一相同的查找算法。隱藏在遞歸之后的思想是簡(jiǎn)單的：一個(gè)遞歸的函數(shù)通過(guò)在一個(gè)更小的子任務(wù)中調(diào)用它本身來(lái)解決某個(gè)任務(wù)。正如我們即將看到的，遞歸是另一種表達(dá)重復(fù)程序結(jié)構(gòu)的方法。遞歸的強(qiáng)大功能存在于它能夠極好地捕獲某些任務(wù)的控制流程

3、。對(duì)于某些編程問(wèn)題，遞歸的解決方法比使用相應(yīng)的傳統(tǒng)重復(fù)方法簡(jiǎn)單得多。在這一章，我們將通過(guò)五個(gè)不同的例子向你介紹遞歸的概念。我們檢查遞歸函數(shù)是怎樣在LC3里實(shí)現(xiàn)的。運(yùn)行時(shí)棧機(jī)制的好處就在于遞歸函數(shù)不需要特別的處理——它們以與其他任何函數(shù)相同的方式執(zhí)行。本章的主要目的是為你提供遞歸的初步但深入的研究，這樣你就可以分析和推理遞歸程序了。能夠理解遞歸代碼對(duì)于寫(xiě)遞歸代碼是必要的因素，而且最終將使遞歸變成你解決編程問(wèn)題的工具集中的一部分。17.2什

4、么是遞歸？什么是遞歸？調(diào)用它本身的函數(shù)就是遞歸函數(shù)，就像圖17.1中的那個(gè)RunningSum函數(shù)那樣。這個(gè)函數(shù)計(jì)算從1到輸入的參數(shù)n之間的和。例如，RunningSum(4)計(jì)算4321。然而，它是遞歸計(jì)算的。注意4的連續(xù)和實(shí)際上是4加上3的連續(xù)和。同樣3的連續(xù)和是3加上2的連續(xù)和。這個(gè)遞歸定義是遞歸算法的基礎(chǔ)。換句話說(shuō)，RunningSum(n)=nRunningSum(n1)在數(shù)學(xué)上，我們用遞歸方程來(lái)表達(dá)這樣的函數(shù)。前面那個(gè)方程是

5、一個(gè)RunningSum的遞歸方程。為了完成這個(gè)方程的計(jì)算，我們還必須提供一個(gè)初始條件。所以除了前面那個(gè)公式外，我們?cè)趶氐淄瓿蛇f歸計(jì)算之前還必須規(guī)定RunningSum(1)=1我們進(jìn)行如下計(jì)算：RunningSum(4)=4RunningSum(3)=43RunningSum(2)=432RunningSum(1)=4321RunningSum的C版本以與遞歸方程相同的方法工作。在函數(shù)調(diào)用RunningSum(4)的執(zhí)行期間，Runn

6、ingSum使用變?cè)?（即，RunningSum(3)）進(jìn)行一次對(duì)它本身的函數(shù)調(diào)用。然而，在RunningSum(3)結(jié)束前，它調(diào)用RunningSum(2)。在RunningSum(2)結(jié)束前，它又Move(n1intermediate)——然后移動(dòng)第n個(gè)盤(pán)子到目標(biāo)上，最后把n1個(gè)盤(pán)子從中間移動(dòng)到目標(biāo)上，或Move(n1target)。所以為了Move(ntarget)，需要兩次遞歸的調(diào)用來(lái)解決兩個(gè)包括n1個(gè)盤(pán)子的子問(wèn)題。與數(shù)學(xué)上的遞

7、歸方程一樣，所有的遞歸定義都需要一個(gè)結(jié)束遞歸的基本條件。對(duì)于我們說(shuō)明的問(wèn)題，這種方法的基本條件包括移動(dòng)最小的盤(pán)子（第1個(gè)盤(pán)子）。既然第1個(gè)盤(pán)子總是位于頂部，不需移動(dòng)任何其它的盤(pán)子，就可以被直接從一根柱子移動(dòng)到任意其它的柱子上，因此不需要移動(dòng)其它的盤(pán)子。如果沒(méi)有基本條件，遞歸函數(shù)將是一個(gè)無(wú)限遞歸，類似于傳統(tǒng)重復(fù)中的無(wú)限循環(huán)。用C代碼實(shí)現(xiàn)我們的遞歸定義是很簡(jiǎn)單的。圖17.4是這個(gè)算法的遞歸的C函數(shù)。讓我們看看當(dāng)我們玩一個(gè)有3個(gè)盤(pán)子的游戲時(shí)發(fā)

8、生了什么。下面是對(duì)MoveDisk的一個(gè)最初的函數(shù)調(diào)用。我們開(kāi)始于想把盤(pán)子3（最大的盤(pán)子）從柱子1移動(dòng)到柱子3，使用柱子2作為中間存儲(chǔ)的柱子。這就是說(shuō)，我們想解決一個(gè)三個(gè)盤(pán)子的漢落塔問(wèn)題。見(jiàn)圖17.5。盤(pán)子：3；當(dāng)前的柱子：1；目標(biāo)柱子：3；中間的柱子：2MoveDisk(3132)這個(gè)調(diào)用引起了另一個(gè)調(diào)用MoveDisk，把盤(pán)子1和2從盤(pán)子3移走到柱子2上，使用柱子3作為中間存儲(chǔ)。這個(gè)調(diào)用被源代碼中的15行所執(zhí)行。盤(pán)子：2；當(dāng)前的柱子

9、：1；目標(biāo)柱子：2；中間的柱子：3MoveDisk(2123)為了把盤(pán)子2從柱子1移到柱子2，我們必須先把盤(pán)子1從盤(pán)子2移到柱子3上（中間的柱子）。所以這引起了另一個(gè)來(lái)自于15行中的對(duì)MoveDisk的調(diào)用。盤(pán)子：1；當(dāng)前的柱子：1；目標(biāo)柱子：3；中間的柱子：2MoveDisk(1132)因?yàn)楸P(pán)子1能夠被直接移動(dòng)，第二個(gè)printf語(yǔ)句被執(zhí)行。見(jiàn)圖17.6。Movedisknumber1frompost1topost3.（將1號(hào)盤(pán)子從1

10、號(hào)柱子移到3號(hào)柱子)現(xiàn)在，MoveDisk的調(diào)用返回到它的調(diào)用者，即調(diào)用MoveDisk(2123)?；貞浳覀?cè)诘人性诒P(pán)子2之上的盤(pán)子被移到柱子3上。既然這個(gè)現(xiàn)在已經(jīng)完成了，我們現(xiàn)在就可以把盤(pán)子2從柱子1移到柱子2。printf是下一條被執(zhí)行的語(yǔ)句，標(biāo)志著另一個(gè)盤(pán)子被移走。見(jiàn)圖17.7。Movedisknumber2frompost1topost2.（將2號(hào)盤(pán)子從1號(hào)柱子移到2號(hào)柱子)下一步，進(jìn)行一次調(diào)用，把在盤(pán)子2上的所有盤(pán)子移回到

11、盤(pán)子2。這發(fā)生在源代碼的22行的MoveDisk的調(diào)用中。盤(pán)子：1；當(dāng)前的柱子：3；目標(biāo)柱子：1；中間的柱子：1MoveDisk(1321)再次，既然沒(méi)有盤(pán)子在盤(pán)子1之上，我們看到移動(dòng)被打印出來(lái)。見(jiàn)圖17.8。Movedisknumber1frompost3topost2.（將1號(hào)盤(pán)子從3號(hào)柱子移到2號(hào)柱子)現(xiàn)在，控制返回到MoveDisk(2123)的調(diào)用，而此次調(diào)用已經(jīng)完成了將盤(pán)子2（和它之上的所有盤(pán)子）從柱子1移動(dòng)到柱子2，返回到

12、它的調(diào)用者。而調(diào)用者是MoveDisk(3132)?，F(xiàn)在，在盤(pán)子3上面的所有盤(pán)子都被移到了柱子2上。盤(pán)子3可以從柱子1移動(dòng)到柱子3上。printf語(yǔ)句是下一條執(zhí)行的語(yǔ)句。見(jiàn)圖17.9。Movedisknumber3frompost1topost3.（將3號(hào)盤(pán)子從1號(hào)柱子移到3號(hào)柱子)下一個(gè)還要完成的子任務(wù)是將盤(pán)子2（和它上面的所有盤(pán)子）從柱子2移動(dòng)到柱子3上。我們可以使用柱子1作為中間存儲(chǔ)。下面的調(diào)用發(fā)生于源文件的22行。盤(pán)子：2；當(dāng)前