1.2 遞歸程序設計

上一節(jié)簡單介紹了自頂向下、先整體后局部的程序設計方法，接下來講解遞歸程序設計。遞歸是指函數(shù)自己調(diào)用自己的程序設計方法。有意思的是：遞歸是自頂向下的特殊情形。一般的自頂向下是指一個函數(shù)對另一個函數(shù)的調(diào)用，而遞歸是指函數(shù)對自己的調(diào)用。

我們認為，遞歸的實質(zhì)是數(shù)學歸納法。什么是數(shù)學歸納法？例如，如果要證明前n個奇數(shù)的和等于n²，如1+3+5＝3²，1+3+5+7＝4²，也就是說1+3+…+（2n－1）＝n²，那么怎么證明呢？

第一步，稱為歸納邊界。即當n＝1時看看定理是否成立。當然，定理是成立的，因為1＝1²。

第二步，稱為歸納假設。假設n＝k時定理成立，即前k個奇數(shù)的和等于k²。

第三步，稱為遞歸推導?？纯?i>n＝k+1時定理是否成立。因為1+3+…+（2k－1）+［2（k+1）－1］＝k²+2k+1＝（k+1）²，可見，n＝k+1時定理是成立的。

綜合上述三步，我們認為前n個奇數(shù)的和的確等于n²，這就是數(shù)學歸納法。遞歸實際上也是按照這三步來的，分別稱為遞歸邊界、遞歸假設和遞歸推導。不同的地方僅僅在于，數(shù)學歸納法是試圖證明一個定理成立，而遞歸的目的是根據(jù)輸入生成輸出。

下面通過例子來說明為什么遞歸的實質(zhì)是數(shù)學歸納法。

1.2.1 河內(nèi)塔問題

遞歸程序的一個著名例子就是河內(nèi)塔（Hanoi塔，也譯為漢諾塔）問題。

有3根插在地上的桿子A、B、C。A桿上套有n個中間有孔的碟子，碟子的直徑從上到下分別是1，2，…，n，如圖1－1所示?，F(xiàn)在我們試圖把所有碟子從A桿移到C桿，條件是：

1）任意一根桿子上只有最上面的碟子可以移動。

2）任何情況下，大碟子都不能放在小碟子的上面。

3）B桿可以作為中轉(zhuǎn)用。

例如，當n＝4時，移動步驟是這樣的：

1）Move 1 from A ＝ ＝ ＞ B

2）Move 2 from A ＝ ＝ ＞ C

3）Move 1 from B ＝ ＝ ＞ C

4）Move 3 from A ＝ ＝ ＞ B

5）Move 1 from C ＝ ＝ ＞ A

6）Move 2 from C ＝ ＝ ＞ B

7）Move 1 from A ＝ ＝ ＞ B

8）Move 4 from A ＝ ＝ ＞ C

9）Move 1 from B ＝ ＝ ＞ C

10）Move 2 from B ＝ ＝ ＞ A

11）Move 1 from C ＝ ＝ ＞ A

12）Move 3 from B ＝ ＝ ＞ C

13）Move 1 from A ＝ ＝ ＞ B

14）Move 2 from A ＝ ＝ ＞ C

15）Move 1 from B ＝ ＝ ＞ C

解決此類問題的第一件事情就是確定問題的輸入和輸出。河內(nèi)塔問題的輸出很明確。輸入是什么？可能有人認為輸入是碟子的個數(shù)，例如n。這個想法是錯誤的，因為我們并不清楚這n個碟子在哪根桿子上。所以輸入?yún)?shù)除了n之外，應該還有a、b、c 3個參數(shù)，分別表示“來源”“中轉(zhuǎn)”“目的地”。注意，a、b、c的初值分別是“A”“B”“C”。

確定了輸入和輸出之后，就可以按照遞歸的方法解決這個問題了。既然遞歸的實質(zhì)是數(shù)學歸納法，并且數(shù)學歸納法是按照3個步驟進行思考的，那么與之對應，遞歸也應該按照3個步驟進行思考。

第一步，遞歸邊界（對應于數(shù)學歸納法的歸納邊界）。所謂遞歸邊界就是輸入?yún)?shù)要滿足的一個條件，在這個條件下，原問題可以很容易得到解決。確定河內(nèi)塔問題的邊界在哪里，就是確定輸入?yún)?shù)在什么情況下，問題可以很容易得到解決。顯然，當輸入?yún)?shù)n＝1時，問題最好解決，因為此時a上僅有一個碟子，直接把這個碟子從a移到c即可。

第二步，遞歸假設（對應于數(shù)學歸納法的歸納假設）。即假設n－1個碟子可以從a、b、c中的任意一根桿子移到另外任意一根桿子上。讀者可能會有疑問：“我怎么把n－1個碟子從一根桿子移到另一根桿子上？”。這是假設的。編程序也可以假設？是的，可以假設，這正是遞歸程序設計神奇又有魅力的地方。

關于遞歸假設，需要注意兩點：第一，遞歸假設時所用到的參數(shù)應該比原問題的參數(shù)更靠近邊界（遞歸邊界的簡稱，以下同），例如上面的分析中，n－1就比n更靠近邊界；第二，參數(shù)的個數(shù)、每個參數(shù)的類型和作用都應該與原參數(shù)一一對應。違反了這兩點中的任何一點都會導致遞歸的失敗。

第三步，遞歸推導（對應于數(shù)學歸納法的歸納推導）。就是利用河內(nèi)塔問題在n－1位置處的解來推導問題在n處的解。既然n－1個碟子可以從任意一根桿子移到另外任意一根桿子上，那么我們可以這樣移：以c作為中轉(zhuǎn)，先把a最上面的n－1個碟子移到b桿上，如圖1－2所示，注意a、b、c的初值分別是“A”“B”“C”（后同）；再把a桿剩下的直徑為n的那個碟子移到c桿上，如圖1－3所示；最后把b桿上的n－1個碟子移到c桿上，如圖1－4所示，這樣問題就得到了解決。

遞歸程序設計的原則就是：首先用一個if語句判斷當前參數(shù)是不是處于遞歸邊界。如果是，就按遞歸邊界處理；否則，利用遞歸假設和遞歸推導進行編程即可。解決河內(nèi)塔問題的遞歸程序如下：

從本質(zhì)上講，遞歸程序設計方法仍然是一種自頂向下的程序設計。在編寫一個遞歸程序的函數(shù)體時，被調(diào)用的子函數(shù)就是正在被實現(xiàn)的函數(shù)本身。既然子程序都可以先調(diào)用后定義，那么遞歸子程序當然也是可以先調(diào)用后定義的。唯一區(qū)別就是一般自頂向下調(diào)用的是其他函數(shù)，而遞歸調(diào)用的是當前這個函數(shù)本身。

1.2.2 兔子問題

一對剛出生的小兔子兩個月后就能生下一對小兔子，且之后的每個月都能生一對小兔子。剛生下的小兔子過兩個月以后也能每個月生一對小兔子，以此類推。假設兔子永遠不會“翹辮子”，現(xiàn)在給你一對剛出生的小兔子，問n個月后有幾對兔子？

顯然，輸入?yún)?shù)是n。遞歸邊界是n＝0或n＝1，此時小兔子還沒有出生，所以兔子數(shù)目都是1對。遞歸假設也很好做。下面考慮遞歸推導。當n＞2時，每個月的兔子由上個月的兔子和本月新出生的兔子組成。而本月新出生的兔子數(shù)與兩個月前的兔子總數(shù)相同，因為那時即使是剛出生的兔子現(xiàn)在也能在本月生出一對新的小兔子。所以，本題的解就是著名的斐波那契（Fibonacci）數(shù)列：

運行結(jié)果如下：

0：　1 pairs

1：　1 pairs

2：　2 pairs

3：　3 pairs

4：　5 pairs

5：　8 pairs

6：　13 pairs

7：　21 pairs

8：　34 pairs

9：　55 pairs

10：　89 pairs

1.2.3 字符串匹配問題

如果說上節(jié)的兔子問題還可以用非遞歸的方法實現(xiàn)，那么下面這個問題就很難用非遞歸方法來實現(xiàn)了。

假設“?”可以匹配0個或0個以上的字符，“？”可以匹配且僅匹配一個字符。請寫一個遞歸函數(shù)match（ pattern，str），判斷字符串str是否與模式pattern匹配。

例如，在操作系統(tǒng)里尋找一個文件時，不必寫全文件的名字，可以使用“?”和“？”這兩個通配符。如AB?C？.doc表示任何以AB打頭、倒數(shù)第二個字符是C的doc文檔。

我們?nèi)匀话凑者f歸程序三部曲來考慮這個函數(shù)。

第一，遞歸邊界。在什么情況下可以直接判斷str是否與pattern匹配？顯然，如果str是個空字符串（即長度為0的字符串），那pattern也必須是個空字符串兩者才能匹配。反之，如果pattern是個空字符串，那它也只能和空字符串匹配。所以這個邊界條件是str或pattern為空字符串。

第二，遞歸假設。假設在pattern或者str比原來少一個字符的情況下，match函數(shù)總能正確地判定二者是否匹配。注意遞歸假設所用到的參數(shù)要比原參數(shù)更靠近邊界。

第三，遞歸推導。我們可以考慮pattern的第一個字符。如果它是“？”，則str的第一個字符可以忽略，只需考慮它們剩下的部分是否匹配即可。如果它是“?”，則又分為兩種情況：“?”只匹配0個字符，這意味著可以把“?”刪除，然后考慮pattern剩下的部分是否與str匹配即可；“?”匹配1個或1個以上的字符，此時可以把str的第一個字符刪除，然后看它剩下的部分與pattern是否匹配即可。

綜上所述，可以給出遞歸代碼如下：

_test_match（）函數(shù)的第三個參數(shù)是真實結(jié)果，我們會把匹配結(jié)果也打印出來與它進行對比。運行結(jié)果如下：

ababaab，a?b，True，True

ababaab，?abab?，True，True

ababaab，a?a？b，True，True

ababaab，a?bb，F(xiàn)alse，F(xiàn)alse

ababaab，aabab?，F(xiàn)alse，F(xiàn)alse

ababaab，a?b？b，F(xiàn)alse，F(xiàn)alse

1.2.4 組合問題

從5個不同的小球里任取3個，有多少種取法？這是一個典型的組合問題，答案是C（5，3），即10種。但是我們現(xiàn)在并不是要用數(shù)學方法求組合的解，而是要求編寫一個遞歸函數(shù)comb（m，n），以求得從m個小球里任取n個的組合數(shù)，其中m≥n始終成立。

我們根據(jù)遞歸程序三部曲來考慮這個函數(shù)。

第一，遞歸邊界。在什么情況下，組合數(shù)可以直接求得，而不必進行遞歸？顯然當n＝0時，不論m等于多少，組合數(shù)都是1。把n＝0作為遞歸邊界已經(jīng)足夠了。但是，如果還有其他邊界則也應該考慮在內(nèi)，這樣有助于程序在遞歸過程中更快地接近邊界，從而提高程序運行速度，減少內(nèi)存占用。如果n＝m，則意味著把所有的小球都取出，這樣的組合數(shù)也只有1個。

第二，遞歸假設。假設只要把m和n做更接近于邊界的變化，則組合數(shù)總能求得出來。

第三，遞歸推導。我們把最后一個小球Z拎出來單獨考慮。如果最后取出來的n個小球里不包含Z，則相當于從Z之前的m－1個小球里取n個，根據(jù)遞歸假設，共有comb（m－1，n）種組合。反之，如果取出來的n個小球里包含Z，則相當于從Z之前的m－1個小球里取n－1個，根據(jù)遞歸假設，共有comb（m－1，n－1）種組合。所以遞歸程序如下：

解決了組合問題，請大家思考：如何解決排列問題？

1.2.5 人字形鐵路問題

如圖1－5所示，有一段人字形的鐵路，火車只能從右邊鐵路線駛進，并且只能從左邊鐵路線駛出。駛進來的火車可以停在人字形的上半部分（直線）鐵路線上，從而讓后進來的火車先從左邊鐵路線駛出。當然它也可以進來之后不作停留直接駛出。假設右邊有n列火車，問從左邊駛出的n列火車的排列有多少種？

例如，假設右邊有3列火車A、B、C，則從左邊駛出的火車的排列只有5種：ABC、ACB、BAC、BCA和CBA。3列火車的所有6種排列里唯有CAB是不可能的。

顯然，本題的輸入?yún)?shù)是右邊等待進入鐵路的火車的數(shù)量n。這當然沒有錯誤，可問題是接下來的遞歸推導會比較困難。為了解決這個難題，我們再增加一個參數(shù)m，表示從右邊開進鐵路，停在堆棧里，沒有開出的火車數(shù)量。m的初值是0。

顯然，遞歸邊界是n＝0。此時，不論停在鐵路上的火車（即m）有多少，這些火車都只能按照次序一一從左邊輸出。所以輸出的排列數(shù)目都只有一個。

遞歸假設比較好理解，這里略過不提。對于遞歸推導，當兩個參數(shù)分別是n、m時，有兩種方法分解問題。第一，右邊等待的n列火車中的第一列開進鐵路，這時問題參數(shù)分別轉(zhuǎn)化為n－1、m+1；第二，停在鐵路上的m列火車中的第一列開出，這時問題參數(shù)分別轉(zhuǎn)化為n、m－1，前提是m＞0。所以我們分別用這兩組參數(shù)進行遞歸調(diào)用即可。程序如下：

運行結(jié)果如下：

1 1

2 2

3 5

4 14

5 42

6 132

7 429

8 1430

9 4862

10 16796

這個問題有意思的地方在于，雖然m的值加1了，但是子問題的參數(shù)還是比原問題更靠近遞歸邊界。這是因為遞歸邊界僅與參數(shù)n有關，與m無關。