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

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

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

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

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

5、一個RunningSum的遞歸方程。為了完成這個方程的計(jì)算，我們還必須提供一個初始條件。所以除了前面那個公式外，我們在徹底完成遞歸計(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使用變元3（即，RunningSum(3)）進(jìn)行一次對它本身的函數(shù)調(diào)用。然而，在RunningSum(3)結(jié)束前，它調(diào)用RunningSum(2)。在RunningSum(2)結(jié)束前，它又Move(n1intermediate)——然后移動第n個盤子到目標(biāo)上，最后把n1個盤子從中間移動到目標(biāo)上，或Move(n1target)。所以為了Move(ntarget)，需要兩次遞歸的調(diào)用來解決兩個包括n1個盤子的子問題。與數(shù)學(xué)上的遞

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

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

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

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

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

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