## 10.2 遞歸 我們已經知道，循環是必不可少的基本流程控制結構之一，在編程中時時會用到循環語 句。但出乎意外的是，一個編程語言實際上可以不提供循環語句①！因為有另一種語言構造 可以替代循環，這就是遞歸。 讀者也許聽說過“循環定義”，即在定義概念 A 的時候直接或間接地用到了 A 自身。例 如將“邏輯學”定義成“研究邏輯的科學”，這實際上是同語反復，并未揭示任何新的內涵； 又如將“美麗”定義成“漂亮”，再將“漂亮”定義成“美麗”，這種循環定義實際上也是同 語反復。循環定義是一種常見的邏輯錯誤，應盡量避免使用，但在數學和程序設計中，我們 經常在一個函數的定義中直接或間接地用到該函數自身，這種函數稱為遞歸（recursive②） 函數。通過下面的討論我們會看到，這種遞歸定義不同于循環定義，它能夠明確地定義出函 數的意義。 遞歸是一種強大的算法設計思想和方法，利用遞歸可以輕松解決很多難題。下面我們通 過例子來介紹這種方法。 階乘 數學中的階乘運算通常用下式定義： ``` n! = n x (n - 1) x (n - 2) x ... x 2 x 1 ``` 注意，當 n 為 0 時，其階乘被定義為 1。 如果要編程計算 n 的階乘，可以采用以前介紹過的累積算法模式來實現，累積算法的關 鍵部分是一個循環語句。下面是此方法的實現代碼及執行實例： >>> def fac(n): if n == 0: return 1 else: f = 1 for i in range(1,n+1): f = i * f return f ``` > ① 有一類函數式編程語言（如 Scheme）就不提供循環語句構造。 > ② 英文 recur 的原意為再次發生、重新出現等。被定義的術語又出現在定義之中，就是遞歸。 ``` >>> fac(4) 24 >>> fac(40) 815915283247897734345611269596115894272000000000L ``` 下面我們用另一種方式來觀察階乘的定義。在階乘定義式中，等號右邊的第一個 n 之后 的部分是什么？稍加思考即可看出就是(n-1)的階乘，即階乘定義式可寫成： ``` n! = n x (n - 1)! ``` 這個式子的含義是：n 的階乘定義為 n 乘(n-1)的階乘。我們看到，“階乘”的定義中用到了 “階乘”本身，這就是遞歸定義。 現代編程語言都支持遞歸函數，Python 也不例外。讀者也許會將上面的遞歸定義式直 接翻譯成如下 Python 函數： ``` def fac(n): return n * fac(n-1) ``` 但這個定義是錯誤的。如果執行這個函數，將會形成如下調用鏈條： ``` fac(n) => fac(n-1) => ... => fac(1) => fac(0) => fac(-1) => fac(-2) => ... ``` 顯然，遞歸將無窮無盡地延續下去①。 有效遞歸定義的關鍵是具有終止條件，使得到達某一點后不再遞歸，否則會導致像無窮循環一樣的后果。對階乘來說，當 n=0 時，n!的值定義為 1，此時無需遞歸。在上面的 fac 函數中添加這個終止條件，即可得正確的遞歸版階乘函數： ``` >>> def fac(n): if n == 0: return 1 else: return n * fac(n-1) >>> fac(4) 24 >>> fac(40) 815915283247897734345611269596115894272000000000L ``` 為了理解遞歸函數的執行過程，需要回顧第 4 章中介紹的函數調用與返回的知識。圖10.1 展示了 fac(2)的計算過程。  圖 10.1 fac(2)的計算過程 > ① 事實上編程語言中的遞歸層數是有限制的，當突破限制時遞歸過程會終止。 計算 fac(n)時，由于每次遞歸都導致計算更小的數的階乘，因此這個遞歸過程遲早會到 達計算 fac(0)的情形。而根據 fac()的定義，fac(0)直接返回 1，無需遞歸計算。我們稱這種情 形為遞歸定義的奠基情形。對于奠基情形，遞歸函數能夠直接計算結果。 要說明的是，上面的階乘函數定義其實仍然有 bug：當 n 的初始值小于 1 時，調用 fac(n) 會導致無窮遞歸！解決這個問題很容易，只需在程序開始處檢查 n 是否為負數即可，并且僅 當 n 為非負自然數時才能計算階乘。編寫遞歸程序時很容易在終止條件上面犯錯誤，作為好 的編程習慣，我們應當圍繞遞歸奠基情形測試各種情形。 還要說明一點，每次遞歸調用 fac()都相當于調用一個新的函數，系統將為該函數的局 部變量和參數分配新的空間，與其他 fac()調用的局部變量和參數完全沒有關系。初學者在 這一點上也會經常犯錯誤，以為各遞歸調用中使用的變量是全局共享的。在圖 10.1 中有三 次對 fac(n)的調用，這三次調用應當視為獨立的三個函數，其中用到的參數 n 應當視為三個 相互獨立的局部變量。 列表處理 遞歸對于處理列表是非常有用的，因為列表本身就是“遞歸結構”——任一列表都可看 作是由第一個數據成員與剩余數據列表組成的，即：[a1,a2,...,an]可視為由 a1 和[a2,...,an]組成。 編程處理這個列表時，只需要單獨考慮如何處理 a1，而對[a2,...,an]的處理可以通過遞 歸調用來解決。顯然，每次遞歸都導致處理一個更短的列表，如此遞歸下去終將到達空列表 情形，這正可作為奠基情形。在 Python 中通過索引很容易取得列表 list 的第一個數據和剩 余數據列表，它們分別是 list[0]和 list[1:]。 作為例子，下面我們寫一個遞歸函數來逆向顯示列表的數據，即將[a1,a2,...,an]顯 示為 ``` an,...,a2,a1 ``` 根據列表的“遞歸結構”性質，不難形成這樣的遞歸思考：為了逆向顯示 list，只需先 逆向顯示 list[1:]，然后顯示 list[0]；當剩余數據列表為空時停止遞歸。這個遞歸思考可以直 接翻譯成如下 Python 代碼： ``` >>> def revList(list): if list != []: revList(list[1:]) print list[0], else: return >>> revList([1,2,3,4,5]) 5 4 3 2 1 ``` 對于簡單列表的處理任務，用 for 循環語句也很容易實現；但當列表很復雜（例如列表 中的元素本身可能是列表），用循環語句就很難編程，而用遞歸則可以很容易地解決問題。 作為練習，讀者不妨思考一下如何逆向顯示如下形狀的列表： ``` [1,[2,3],4,[5,6,[7,8],9]] ``` 二分搜索 10.1 節中介紹了線性搜索算法，讀者已經知道線性搜索的優點是適合無序的數據列表，缺點是不適合大量數據。當列表中的數據有序時，存在更好的搜索策略，這個策略的基本思 想可以通過一個猜數游戲展現出來。 假設某甲心中想好了一個 100 以內的自然數，讓某乙來猜這個數。某乙每猜一次，某甲 都會告訴他猜對了、猜大了或猜小了三種情形之一。某乙該采用什么策略來玩這個游戲呢？ 某乙可以每次都隨機猜一個數，也可以系統化地按 1、2、3、……的順序猜（此即線性搜索）， 但這兩種策略平均需要猜很多次才能猜中。最好的策略是先猜 1～100 的中間數 50，如果猜 中自不必說，如果猜大了則接下去猜 1～49 的中間數 25，如果猜小了則接下去猜 51～100 的中間數 75。依此類推，每次都猜可能值范圍的中間值，直至猜中。這個策略就是我們要 介紹的二分搜索（binary search）算法。 下面我們利用二分搜索來解決在一個有序數據列表 list 中查找指定數據 x 的問題。先看 如何利用循環來實現二分搜索。算法的核心是一個循環，每一次循環都檢查當前搜索范圍的 中間數據是否等于 x；不等的話，根據大小信息重新設定搜索范圍；如果找到了 x，或者沒 有剩余數據了，則循環終止。為了便于設定搜索范圍，可以用兩個變量 low 和 high 分別記 錄搜索范圍的兩端，每次循環后根據比較結果調整這兩個變量即可重新設定搜索范圍。代碼 如下： ``` def binary(list,x): low = 0 high = len(list) - 1 while low <= high: mid = (low + high) / 2 if list[mid] == x: return mid elif list[mid] > x: high = mid - 1 else: low = mid + 1 return -1 ``` 再看二分搜索的遞歸實現。二分搜索算法可以這樣表達：檢查當前搜索范圍的中間數據， 如果該數據就是目標數據，則算法結束；如果不是，則選擇某一半范圍重新進行二分搜索。 這段話可以翻譯成如下偽代碼： ``` 二分搜索算法：在范圍 list[low]到 list[high]之間查找 x 取當前范圍的中間數據 m； 如果 m 等于 x 或者 m 不存在則算法結束； 如果 x &lt; m 則在范圍 list[low]到 list[mid-1]之間查找 x， 否則在范圍 list[mid+1]到 list[high]之間查找 x。 ``` 這個算法中有三處（見劃線部分）涉及幾乎相同的操作，這正是二分搜索的遞歸性質的 體現。奠基情形是找到了目標值或者檢查完所有數據都未找到目標值，這時將不再遞歸。由 于每次遞歸調用都將搜索空間減小了一半，因此遲早會到達奠基情形。下面給出遞歸版本二 分搜索的 Python 代碼實現。注意與循環版本不同的是，每次遞歸都需要指明搜索范圍，因 此我們將搜索范圍的兩個端點 low 和 high 也作為函數參數。 ``` >>> def recBinSearch(list,x,low,high): if low > high: return -1 mid = (low + high) / 2 m = list[mid] if m == x: return mid elif x < m: return recBinSearch(list,x,low,mid-1) else: return recBinSearch(list,x,mid+1,high) >>> recBinSearch([1,3,5,7,9],5,0,4) 2 >>> recBinSearch([1,3,5,7,9],6,0,4) -1 ``` 階乘和二分搜索這兩個例子說明，許多問題既可用循環（或稱迭代）來實現，也可用遞 歸來實現。很多情況下，兩種方法在設計上都很容易；但對有些問題，迭代算法很難設計， 而遞歸算法則非常容易得到，例如下面的 Hanoi 塔問題。 Hanoi 塔問題 Hanoi 塔問題是體現遞歸方法強大能力的經典例子，該問題涉及如下故事：在某個寺廟 里有三根柱子（不妨稱為 A、B、C 柱），A 柱上有 n 個同心圓盤，圓盤尺寸各不相同，并且 小盤疊在大盤之上，B 柱和 C 柱為空（參見圖 10.2）。寺廟的僧侶們有一項任務：將 n 個圓 盤從 A 柱移到 C 柱，移動過程中可以利用 B 柱作為臨時存放柱。具體的移動圓盤的規則是： + 圓盤只能放在柱子上； + 每次只能移動位于任一柱子頂部的圓盤； + 大圓盤永遠不能置于小圓盤之上。  圖 10.2 Hanoi 塔問題 下面我們來設計解決此問題的算法，該算法能夠給出搬運步驟。例如對于 n = 3 的情形，算法將顯示如下移動過程（其中 A -&gt; C 表示將 A 柱頂部圓盤移至 C 柱頂部，余類推）： ``` A -> C A -> B C -> B A -> C B -> A B -> C A -> C ``` Hanoi 塔問題看上去有點難度，但如果采用遞歸方法，算法是非常簡單的。稍加思考即 可明白，為了將 A 柱上的所有圓盤移到 C 柱，必然需要有一步將底部的最大圓盤從 A 柱移 到 C 柱，而為此又必須先將最大圓盤上面的 n - 1 個圓盤從 A 柱移到 B 柱，從而形成最大 圓盤之上沒有其他圓盤、同時 C 柱上也沒有圓盤的局面（參見圖 10.3）。  圖 10.3 為移動最大圓盤必須形成的格局 至此，可以將最大圓盤從 A 柱移到 C 柱，顯然接下去再也不需要移動這個圓盤了，因此可視為不存在。這時形成的局面（圖 10.4）與初始局面非常相似，即：B 柱上有 n - 1 個 圓盤，A 柱和 C 柱為空（無視最大圓盤）。于是任務變成了：將 n - 1 個圓盤從 B 柱移動到 C 柱，移動過程中可以利用 A 柱作為臨時存放柱。將這里的黑體部分文字與前面的初始問 題文字相比較，即可看出 Hanoi 塔問題的遞歸性質：一旦最大圓盤到達目的地，剩下來的問 題恰好又是初始 Hanoi 塔問題，只不過問題規模變成了 n - 1，并且 A 柱和 B 柱的角色相互 交換。  圖 10.4 最大圓盤就位之后的格局 根據以上分析，容易得到解決 Hanoi 塔問題的算法。下面是算法的偽代碼： ``` 算法：將 n 個圓盤從 A 柱移到 C 柱，以 B 柱作為臨時存放柱。 將 n - 1 個圓盤從 A 柱移到 B 柱，以 C 柱作為臨時存放柱； 將最大圓盤從 A 柱移到 C 柱； 將 n - 1 個圓盤從 B 柱移到 C 柱，以 A 柱作為臨時存放柱。 ``` 從算法中可見，通過遞歸，我們將規模為 n 的問題轉化成了兩個規模為 n – 1 的問題。 如此遞歸下去，最終將轉化成規模為 1 的問題。而 n = 1 的 Hanoi 塔問題是平凡的，直接移 動一步即可，不再需要遞歸，這就是奠基情形。有了奠基情形，每次遞歸又導致問題規模變 小，可見上述遞歸算法能正確終止。下面我們給出對上述算法的 Python 實現，并對 n = 3 的 情形進行驗證。代碼中 hanoi 函數的參數分別表示圓盤個數和三根柱子（源、目的地、臨時 存放）。 ``` >>> def hanoi(n,source,dest,temp): if n == 1: print source,"->",dest else: hanoi(n-1,source,temp,dest) hanoi(1,source,dest,temp) hanoi(n-1,temp,dest,source) >>> hanoi(3,"A","C","B") A -> C A -> B C -> B A -> C B -> A B -> C A -> C ``` 至此，一個看上去挺難的問題通過遞歸就輕松地解決了。讀者有興趣的話不妨試試如何 利用循環（迭代）來解決 Hanoi 塔問題。 最后對遞歸方法做個小結。 遞歸是非常重要的算法設計方法，在解決很多具有遞歸性質的問題、結構的時候，設計 遞歸算法往往是直接而簡單的。遞歸定義必須滿足以下條件才是良定義的： + 有一個或多個無需遞歸的奠基情形； + 遞歸總是針對規模更小的問題。 有了這兩個條件，遞歸鏈最終將到達奠基情形，從而使遞歸過程終止。 雖然遞歸算法容易設計、實現，也容易理解，但遞歸是有代價的。由于遞歸涉及大量的 函數調用，因此需要耗費較多的內存和較長的執行時間，即遞歸算法的效率較差。而迭代算 法不涉及函數調用，故速度更快，更節省內存。