本節書摘來自華章計算機《計算機系統：核心概念及軟硬體實作（原書第4版）》一書中的第2章，第2.4節,作者：[美] j. 斯坦利·沃法德（j. stanley warford）著， 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
你曾在字典中查找不認識單詞的定義時，發現字典恰恰是以另一個不認識的單詞來定義它的嗎？接着你就查找第二個單詞，發現它是用第一個單詞來定義的嗎？這是一個循環或間接遞歸的例子。字典的這個問題源于從一開始你就不知道第一個單詞的意思。如果第二個單詞用你認識的第三個單詞來定義，就能得到滿意的結果了。
數學上，函數的遞歸定義（recursive definition）是指函數使用它自己來定義自己。例如，假設函數f(n)定義如下：
f(n)＝nf(n-1)
若用這個定義來确定f(4)，就在定義中用4代替n：
f(4)＝4f(3)
但是現在你不知道f(3)是什麼，那麼在定義中用3代替n，得到：
f(3)＝3f(2)
把這個代進f(4)的公式中，得到：
f(4)＝4(3)f(2)
但是，現在你不知道f(2)是什麼，定義告訴你它是2乘以f(1)，那麼求f(4)的公式變為
f(4)＝4(3)(2)f(1)
可以看到這個定義的問題：沒有什麼能夠結束這個過程，你将無窮盡地計算f(4)。
f(4)＝4(3)(2)(0) (-1)(-2)(-3)...
這就如同字典給了你一個無窮盡的定義串一樣，每個單詞都基于另一個你不認識的單詞。為了完整，定義必須指定某個特定n的f(n)值，那麼前述過程就能終止，你可以計算出任何n的f(n)。
下面是f(n)的一個完整遞歸定義：
f(n)＝nf(n-1)n>1
f(1)＝1
這個定義說明前述過程可以在f(1)停止。是以，f(4)是
＝4(3)f(2)
＝4(3)(2)f(1)
＝4(3)(2)(1)
＝24
你應該知道這就是階乘函數的定義。
2.4.1階乘函數
c++中的遞歸函數（recursive function）是調用它自己的函數。沒有什麼有新文法的特殊遞歸語句需要學習。它在運作時棧上配置設定存儲空間的方法和非遞歸函數是一樣的。唯一的不同是遞歸函數包括一條調用它自己的語句。
圖2-22中的函數遞歸地計算一個數的階乘，它是f(n)遞歸定義的一個直接應用。
圖2-23給出了簡化的該程式運作時棧的曆史記錄，它隐藏了主程式的棧幀。第一個函數調用來自主程式。圖2-23c展示了第一次調用的棧幀，傳回位址是ra1，它代表主程式中cout調用的位址。
圖2-23圖2-22的運作時棧
該函數中第一條語句測試n是否為1。因為n的值是4，是以執行else部分。而else部分的語句
在傳回語句的右邊包含一個對函數fact的調用。
這是一個遞歸調用，因為它在函數裡調用它自己。這個調用和任何其他函數調用所做的事情順序是一樣的。配置設定新的棧幀，如圖2-23d所示。第二個棧幀中的傳回位址是這個函數中調用語句的位址，由ra2來表示。
實參是n-1，由于圖2-23c中n的值是4，是以它的值是3。形參n是傳值調用的，是以圖2-23d頂部棧幀的形參n指派為3。
圖2-23d展示了一個對遞歸調用來說很典型的奇特現象。圖2-22的程式代碼中函數fact的形參表中隻聲明了一個n，但圖2-23d中n出現了兩次。n的舊執行個體從主程式獲得的值4，而n的新執行個體從遞歸調用中獲得值3。
計算機暫停該函數舊的執行，并從頭開始該函數的一個新的執行。該函數的第一條語句是比較n是否等于1，圖2-23d中在運作時棧上有2個n，應該比較哪個n呢？規則是：任何對局部變量或形參的引用指的都是頂部棧幀中的那個。因為n的值是3，是以執行else部分。
但是現在函數又進行一次遞歸調用，配置設定第三個棧幀，如圖2-23e所示，接着是第四個，如圖2-23f所示。每次調用，最新配置設定的形參n的值都比舊值小1，因為函數調用是
最後，如圖2-23g所示，n的值為1 。該函數給棧上标号為retval的單元指派為1，跳過else部分，然後終止。這使得控制傳回到它的調用語句。
遞歸傳回發生的事情和非遞歸傳回是一樣的。retval包含傳回值，傳回位址說明接下來要執行哪條語句。圖2-23g中，retval是1，傳回位址是該函數中的調用的語句。釋放頂部棧幀，調用語句
完成它的執行。該語句将n的值2乘以傳回值1，并把這個乘積賦給retval。這樣retval的值就是2，如圖2-23h所示。
每次傳回都執行同樣的事件序列。圖2-23i、j展示了從第二次調用傳回的值6，而第一次調用傳回的值是24。圖2-24展示了圖2-22程式的調用序列。主程式調用函數fact，接着函數fact調用它自己3次。本例中，函數fact總共被調用了4次。
你可以看到，程式計算4的階乘的方法與從它的遞歸定義計算f(4)的方法一樣。計算f(4)從4乘以f(3)開始，接着必須暫停計算f(4)，轉而計算f(3)。在得到f(3)的值之後，用4乘以它就得到f(4)。
類似地，程式必須暫停對該函數的一次執行，再次調用同一個函數。運作時棧跟蹤記錄變量的目前值，這樣當函數執行個體再繼續時，還能使用正确的變量值。
2.4.2遞歸的思考方式
有兩種不同的角度來看待遞歸：微觀的和宏觀的。圖2-23是從微觀的角度展示的，精确地給出了執行期間計算機内發生了什麼。它考慮的是程式曆史記錄中運作時棧的細節。宏觀的看法不考慮單獨的每棵樹，它考慮的是整個森林。
為了了解c++怎樣實作遞歸，需要知道微觀的看法。在學習asmb5層怎樣實作遞歸時，必須了解運作時棧的細節。如果隻是想寫遞歸函數，應該宏觀而不是微觀地思考。
寫遞歸函數最難的地方是，必須假設可以調用正在寫的程式。為此，你必須忘掉運作時棧，宏觀地思考。
數學歸納法證明有助于進行宏觀思考。歸納法證明的兩個關鍵元素是
建立基礎。
給定n的公式，證明它對n＋1是成立的。
同樣，設計遞歸函數的兩個關鍵元素是
計算該基礎的函數。
假設有n-1的函數，寫出n的函數。
想象你正在寫函數fact，寫到了這裡：
不知該怎樣寫下去了。已經計算了基礎n=1時的函數，但是現在必須假設能調用函數fact，盡管還沒有寫完這個函數。必須假設fact(n-1)将傳回階乘的正确值。
這裡是必須宏觀思考的地方。如果開始想知道fact(n-1)怎樣傳回正确值，如果棧幀開始在你腦中跳躍，那麼這樣的思考是不對的。在歸納法證明中，必須假設有n的公式。同樣，在寫函數fact時，必須假設能調用fact(n-1)，毋庸置疑。
遞歸程式是基于分治政策的，如果能把一個大問題分解為小問題進而解決它時，這個政策很合适。每次遞歸調用都使問題變得越來越小，直到程式到達最小的問題，即基礎，基礎是很容易解決的。
2.4.3遞歸加法
這裡有遞歸問題的另一個例子。假設list是一個整數數組，想要遞歸地求出表中所有整數的和。
第一步是構想出以較小問題來解決大問題的解決方案。如果知道怎樣求出list[0]和list[n-1]之間元素的和，可以簡單地把這個和加上list[n]，就能得到所有整數的和。
第二步是設計出具有适當參數的函數。這個函數通過調用它自己計算n-1個整數的和來計算n個整數的和。是以參數表裡必須有一個參數指明對數組中多少個整數相加。應該得到如下的函數頭：
怎樣建立歸納基礎呢？很簡單，如果n等于0，那麼函數應該把a[0]和a[0]之間的元素求和，一個元素的和就是這個元素a[0]。
現在可以寫出
現在，宏觀地思考。假設sum(a,n-1)将傳回a[0]和a[n-1]之間所有整數的和。要有信心！需要做的就是把這個和與a[n]相加即可。圖2-25展示了完成的程式中的這個函數。
盡管寫這個函數時沒有從微觀角度進行考慮，但是仍然可以跟蹤記錄運作時棧。圖2-26展示了對sum頭兩次調用的棧幀。棧幀由傳回值、參數a和n以及傳回位址組成。因為這裡沒有局部變量，是以運作時棧上也沒有為它們配置設定存儲空間。
在c++中，數組總是傳引用調用的。是以，過程sum中的變量a引用主程式中的list。圖2-26b和c中從棧幀中标号為a的單元指向标号為list的單元的箭頭表示a引用list。
2.4.4二項式系數函數
遞歸函數的下一個例子有一個更加複雜的調用序列。這個函數計算二項式擴充的系數。
考慮如下的擴充：
(x + y)1＝x + y
(x + y)2 ＝x2 + 2xy + y2
(x + y)3＝x3 + 3x2y + 3xy2 + y3
(x + y)4＝x4 + 4x3y + 6x2y2 + 4xy3 + y4
這些項的系數叫作二項式系數（binomial coefficient）。如果不帶項隻寫出這些系數，就形成一個由數值組成的三角，稱為帕斯卡三角（pascal抯 triangle）。圖2-27是一個最高到7次幂系數的帕斯卡三角。
從圖2-27可以看到，每個系數是它正上方和左上方系數的和。例如，第5行第2列的二項式系數10等于4加6，6在10的正上方，4在10 的左上方。
n次幂k項二項式系數b(n, k)的數學表達式是：
b(n, k)＝b(n-1) + b(n-1, k-1)0≤k≤n
它是一個遞歸定義，因為函數b(n，k)以自己定義了自己。也可以看到，如果k等于0或者如果n等于k， 那麼二項式系數的值就是1，數學表達式：
b(n, 0)＝1
b(k, k)＝1
是這個遞歸函數的歸納基礎。
圖2-28是遞歸計算二項式系數值的程式。該程式直接建立在b(n, k)的遞歸定義之上。圖2-29是運作時棧的記錄。圖2-29b、c和d展示了前3個棧幀的配置設定，分别代表調用bincoeff(3,1)、bincoeff(2,1)和bincoeff(1,1)。第一個棧幀的
傳回位址是主程式中的調用程式，接下來兩個棧幀的傳回位址是y1指派語句，即标号為ra2的那條語句。
圖2-29e展示了從bincoeff(1,1)的傳回，y1獲得函數的傳回值1，接着y2指派語句調用函數bincoeff(1,0)。圖2-29f展示bincoeff(1,0)執行期間的運作時棧，每個棧幀都有不同的傳回位址。
這個程式的調用序列不同于前面那些遞歸程式的調用序列。另一個程式是不斷配置設定棧幀，運作時棧到達最大高度，然後不斷釋放棧幀直到運作時棧為空。這個程式是配置設定運作時棧，達到最大高度，但是不會連續把棧裡的棧幀都釋放。從圖2-29d到圖2-29e釋放棧幀，但是從圖2-29e到圖2-29f配置設定棧幀；從圖2-29f到圖2-29g到圖2-29h又釋放棧幀，而從圖2-29h到圖2-29i又配置設定棧幀。為什麼會這樣呢？這是因為這個函數有兩個遞歸調用而不是一個。如果基礎判斷為真，那麼函數不執行遞歸調用；但如果基礎判斷為假，則函數執行兩個遞歸調用，一個計算y1，一個計算y2。圖2-30展示了該程式的調用序列。可以看到它是樹狀的。樹的每個結點代表一個函數調用。除主程式外，每個結點有兩個孩子結點或者沒有，分别對應于有兩個遞歸調用或者沒有遞歸調用。
參照圖2-30，調用和傳回序列是
可以把調用樹的執行順序形象化，把調用樹想象成海洋的海岸線。一艘船從主程式的左邊沿着海岸線開始航行，并一直保持海岸在它的左邊。船會按照結點被調用和傳回相同的順序通路結點，圖2-31給出了通路路徑。
當從微觀的角度分析遞歸程式時，在建構運作時棧的記錄之前，建構調用樹更容易一些。一旦建構了調用樹，就很容易看清楚運作時棧的行為。每當船在樹中向下通路結點時，程式配置設定棧幀；每當船在樹中向上通路結點時，程式釋放棧幀。
可以根據調用樹确定運作時棧的最大高度。隻需記錄到達調用樹最低結點時配置設定的棧幀數量，這個數對應的就是運作時棧的最大高度。
按照執行順序來畫調用樹不是最簡單的方法。前面那個程式的執行序列從下面開始
不應該用這樣的順序來畫調用樹。從下面這樣開始比較容易一些
從程式代碼可以看到，bc(3, 1)會調用它自己兩次：bc(2, 1)一次，bc(2, 0)一次。然後回到bc(2, 1)确定它的孩子，換句話說，就是要先确定本結點的所有孩子，然後再分析每個孩子的更深層次的調用。
相對于“深度優先”的構造方法，這是用“廣度優先”的方法來構造樹。在複雜的調用樹中多次傳回到較高層結點時，深度優先的問題就來了。你可能不記得該結點的執行狀态是什麼，也就不能确定它的下一個孩子結點是什麼。如果一次性确定了一個結點的所有孩子，那麼就不需要記得所有結點的執行狀态。
2.4.5逆轉數組元素順序
圖2-32是一個遞歸過程而不是函數，它把一個字元數組的元素順序反轉過來。
這個過程把數組str中str[j]和str[k]之間的字元順序逆轉。主程式是想逆轉b和d之間的字元，是以它調用reverse，參數j為0，k為7。
這個過程通過把問題分解成更小的問題來解決。因為0小于7，該過程知道要把0和7之間的字元逆轉，是以它把str[0]和str[7]互換，接着遞歸調用自己來交換str[1]和str[6]之間的字元。如果j大于或等于k，就不需要交換，過程也就什麼都不用做。圖2-33展示了開始時運作時棧的記錄。
2.4.6漢諾塔
漢諾塔遊戲是一個能用遞歸技巧友善解決的經典計算機科學問題。這個遊戲由3個柱子和一組直徑不同的盤子組成。柱子編号為1、2和3，每個盤子的中央有一個洞，能套在柱子上。遊戲的初始設定是所有的盤子都套在一根柱子上，沒有盤子直接放在直徑比它小的盤子上。圖2-34是4個盤子的初始設定。
要解決的問題是把所有盤子從起始的柱子移到另一根柱子，并遵循下列規則：
每次隻可以移動一個盤子，隻能把一根柱子頂部的盤子移動到另一根柱子頂部。
不能把大直徑的盤子放在小直徑盤子的上面。
解決這個問題的過程有3個參數n、j和k，其中
n是要移動的盤子數量。
j是起始柱子。
k是目标柱子。
j和k是整數，用于辨別柱子。給定j和k的值，中間柱子的編号可以用6-j-k計算表示，所謂中間柱子就是既不是起始柱子也不是目标柱子的柱子。例如，如果起始柱子是1而目标柱子是3，那麼中間柱子是6-1-3＝2。
bjarne stroustrup
bjarne stroustrup 1950年出生于丹麥。雖然并非出身于學術家庭，但他依靠自身的努力從丹麥阿魯斯大學（aarhus university）獲得數學專業碩士學位，然後又從劍橋大學（cambridge university）獲得計算機專業博士學位。
stroustrup小時候并沒有接觸過計算機，在大學數學系裡他才第一次見到計算機。那台計算機占據了一整個房間，他學會了用algo 60語言在上面程式設計。他博士期間的工作是用simula67語言寫了一個分布式系統模拟器。依靠寫一些其他專職人員才能寫出來的小型商業程式的收入，他供自己完成了正規的教育。他認為這段經曆幫助他了解了程式設計在現實世界的重要性。
1979年完成了劍橋的學業後，stroustrup舉家搬到了紐澤西，成為了at&t貝爾實驗室在murry hill的研究科學家。c語言和unix作業系統就是在這個實驗室被研發出來并且流行開來的。
stroustrup并不滿足于當時的程式設計語言，他發明了一種新的帶類的c（c with classes）語言，在c語言中加入了面向對象的程式設計特性，就像simula67中的一樣。最終，這個語言演變成了c++，stroustrup作為c++的發明者為人們所熟知。stroustrup很早就決定希望他的語言能夠支援真實的使用者。他了解如果人們不需要去學習一門全新的語言，他的語言就能被廣泛接受和使用，是以他使得除了有少數例外，c++與c語言相容。也就是說，大多數用c語言書寫的程式能夠用c++編譯器進行翻譯（顯然反過來不行）。這個目标對語言設計來說是限制，但是在它的使用上是大有裨益的。stroustrup曾經說：“即使沒有c語言可以與之相容，我也會選擇其他某種語言來相容的。我曾經，現在依然，相信如果我的時間用來花在創造另一種書寫循環的方式上，那就太不值得了。”事實上，c++語言在市場上非常成功。微軟的word、adobe的photoshop和google的搜尋引擎都是以c++來編寫的。
stroustrup當選了美國國家工程院院士，at&t貝爾實驗室院士，榮獲acm的grace murray hopper獎。在本書編寫之時，他是德州農工大學（texas a&m university）計算機科學首席教授（college of engineering chair in computer science）。
“我總是希望能像使用電話那樣簡單地使用計算機。我的願望終于成真了。我不知道該怎樣使用電話了。”
—bjarne stroustrup
要把n個盤子從柱子j移到柱子k，首先檢查是否n=1，如果是，那麼簡單地把這個盤子從柱子j移到柱子k即可。但如果不是，就把問題分解為幾個小部分：
把n-1個盤子從柱子j移到中間柱子。
把一個盤子從柱子j移到柱子k。
把n-1個盤子從中間柱子移到柱子k。
圖2-35展示了從柱子1移動4個盤子到柱子3的問題的分解。
假定初始n個盤子堆放的順序是正确的，這樣的操作過程保證盤子不會放在比它直徑小的盤子上。例如，如圖2-35所示，要把4個盤子從柱子1移到柱子3，這個過程告訴你應該把最上面的3個盤子從柱子1移到柱子2，把底部的一個從柱子1移到柱子3，接着再把那3個從柱子2移到柱子3。
把最上面的3個盤子從柱子1移到柱子2，柱子1上就隻剩下底部的一個盤子。這個盤子是直徑最大的，是以在移動其他盤子的過程中，放在它上面的任何盤子都是更小的。為了把底部這個盤子從柱子1移到柱子3，柱子3必須是空的。這樣就不會把這個底部的盤子放在一個較小的盤子上。當把那3個盤子從柱子2移到柱子3上時，會把它們放在目前在柱子3底部的這個最大的盤子上，這樣3個盤子就被正确地放在柱子3上了。
這個過程是遞歸的。第一步要把3個盤子從柱子1移到柱子2。為此，要把2個盤子從柱子1移到柱子3，再把另一個從柱子1移到柱子2，接着把那2個從柱子3移到柱子2。圖2-36展示了這個移動的序列。根據前述推理，能夠正确地實施這些步驟。在把2個盤子從柱子1移到柱子3的過程中，可以把這兩個盤子中的任意一個放在柱子1底部的兩個盤子上，不用擔心違反規則。
最終，可以把這個問題歸約到隻需移動一個盤子的基礎步驟，而一個盤子的解決方案是容易的。本章結尾的一道問題就是對漢諾塔遊戲的解決方案進行程式設計。
2.4.7 互相遞歸
在有些問題最适合的解決方案中，過程不直接調用它們自己，但是仍然是遞歸的。假設一個主程式調用過程a，過程a包含一個對過程b的調用。如果過程b又包含一個對過程a的調用，那麼a和b是互相遞歸的。盡管過程a不直接調用它自己，但是通過過程b，它間接地調用了它自己。
和普通遞歸相比，互相遞歸的實作沒有什麼不同。運作時棧上配置設定棧幀的方式也是一樣的，先配置設定參數，接着是傳回位址，再是局部變量。
不過，在c++程式中，聲明互相遞歸過程時有一個小問題。原因在于c++語言要求程式的聲明必須先于它的使用。如果過程a調用過程b，那麼在代碼中，b的聲明必須在a的聲明之前；但是如果過程b調用過程a，那麼在代碼中，a的聲明必須在b的聲明之前。問題是，如果每個過程都調用另一個，代碼中每個程式都必須出現在另一個之前，這顯然是不可能的。
針對這種情況，c++提供了函數原型（function prototype），它允許程式員寫出第一個程式的頭，而沒有過程體。函數原型包括完整的形參清單，但在程式體的位置，放一個分号（;）。在一個過程的函數原型之後，就可以是第二個過程的聲明，然後是第一個過程的過程體。
例2.6這是剛才讨論的互相遞歸的過程a和b的架構：
常量、類型、主程式變量
如果b對a有一個調用，編譯器将會核實實參的數量和類型是否與前面在函數原型裡掃描的a的形參比對。如果a對b有一個調用，那麼這個調用會在a的程式體中，因為b在a的代碼塊之前，是以編譯器已經掃描了b的聲明。 □
盡管互相遞歸不如遞歸常見，但有一些編譯器是基于一種叫遞歸下降（recursive descent）的技術，這個技術很大程度上使用了互相遞歸。看看c++語句的結構，你就能明白為什麼是這樣。把一個if嵌套在一個while中，而這個while又嵌套在另一個if中，這是很有可能的。在使用遞歸下降技術的編譯器裡有一個過程用于翻譯if語句，另一個過程用于翻譯while語句。當正在翻譯外層if語句的過程遇到while語句時，它将調用翻譯while語句的程式。而當翻譯while語句的過程遇到嵌套在裡面的if語句時，它又調用翻譯if語句的過程，是以是互相遞歸的。
2.4.8遞歸的成本
本節例子的選取隻基于一個标準：例子說明遞歸的能力。可以看到在使用遞歸的解決方案中，運作時棧需要大量的存儲空間，同時也要花費時間配置設定和釋放棧幀。遞歸解決方案在空間和時間上都是昂貴的。
如果一個問題有不用遞歸的簡單解法，那麼非遞歸方法通常優于遞歸方法。圖2-18中的計算階乘的非遞歸函數肯定比圖2-22的遞歸階乘函數好。圖2-25對數組元素求和與圖2-32都可以不用遞歸，隻用循環就可以很容易地程式設計。
二項式系數b(n, k)有一個基于階乘的非遞歸定義：
如果非遞歸地計算階乘，基于這個定義的程式可能比相應的遞歸程式效率高很多。兩種方法的選擇還有一個可以考慮的因素：非遞歸方法需要乘法和除法，而遞歸方法僅需要加法。
有些問題本質上就是遞歸的，僅用非遞歸方法解決非常困難。漢諾塔遊戲問題的解決本質上就是遞歸的。你可以試着不用遞歸去解決它，看看到底會有多難。快速排序法，最知名的排序算法之一，也屬于這種類型，用非遞歸方法對快速排序進行程式設計比用遞歸方法難得多。