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

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

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

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

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

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

6、ingSum使用變元3（即，RunningSum(3)）進行一次對它本身的函數(shù)調用。然而，在RunningSum(3)結束前，它調用RunningSum(2)。在RunningSum(2)結束前，它又Move(n1intermediate)——然后移動第n個盤子到目標上，最后把n1個盤子從中間移動到目標上，或Move(n1target)。所以為了Move(ntarget)，需要兩次遞歸的調用來解決兩個包括n1個盤子的子問題。與數(shù)學上的遞

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

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

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

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

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

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