## 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 < 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 -> 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 塔問題。
最后對遞歸方法做個小結。
遞歸是非常重要的算法設計方法,在解決很多具有遞歸性質的問題、結構的時候,設計
遞歸算法往往是直接而簡單的。遞歸定義必須滿足以下條件才是良定義的:
+ 有一個或多個無需遞歸的奠基情形;
+ 遞歸總是針對規模更小的問題。
有了這兩個條件,遞歸鏈最終將到達奠基情形,從而使遞歸過程終止。
雖然遞歸算法容易設計、實現,也容易理解,但遞歸是有代價的。由于遞歸涉及大量的 函數調用,因此需要耗費較多的內存和較長的執行時間,即遞歸算法的效率較差。而迭代算 法不涉及函數調用,故速度更快,更節省內存。
- 前言
- 第 1 章 計算與計算思維
- 1.1 什么是計算?
- 1.1.1 計算機與計算
- 1.1.2 計算機語言
- 1.1.3 算法
- 1.1.4 實現
- 1.2 什么是計算思維?
- 1.2.1 計算思維的基本原則
- 1.2.2 計算思維的具體例子
- 1.2.3 日常生活中的計算思維
- 1.2.4 計算思維對其他學科的影響
- 1.3 初識 Python
- 1.3.1 Python 簡介
- 1.3.2 第一個程序
- 1.3.3 程序的執行方式
- 1.3.4 Python 語言的基本成分
- 1.4 程序排錯
- 1.5 練習
- 第 2 章 用數據表示現實世界
- 2.1 數據和數據類型
- 2.1.1 數據是對現實的抽象
- 2.1.1 常量與變量
- 2.1.2 數據類型
- 2.1.3 Python 的動態類型*
- 2.2 數值類型
- 2.2.1 整數類型 int
- 2.2.2 長整數類型 long
- 2.2.3 浮點數類型 float
- 2.2.4 數學庫模塊 math
- 2.2.5 復數類型 complex*
- 2.3 字符串類型 str
- 2.3.1 字符串類型的字面值形式
- 2.3.2 字符串類型的操作
- 2.3.3 字符的機內表示
- 2.3.4 字符串類型與其他類型的轉換
- 2.3.5 字符串庫 string
- 2.4 布爾類型 bool
- 2.4.1 關系運算
- 2.4.2 邏輯運算
- 2.4.3 布爾代數運算定律*
- 2.4.4 Python 中真假的表示與計算*
- 2.5 列表和元組類型
- 2.5.1 列表類型 list
- 2.5.2 元組類型 tuple
- 2.6 數據的輸入和輸出
- 2.6.1 數據的輸入
- 2.6.2 數據的輸出
- 2.6.3 格式化輸出
- 2.7 編程案例:查找問題
- 2.8 練習
- 第 3 章 數據處理的流程控制
- 3.1 順序控制結構
- 3.2 分支控制結構
- 3.2.1 單分支結構
- 3.2.2 兩路分支結構
- 3.2.3 多路分支結構
- 3.3 異常處理
- 3.3.1 傳統的錯誤檢測方法
- 3.3.2 傳統錯誤檢測方法的缺點
- 3.3.3 異常處理機制
- 3.4 循環控制結構
- 3.4.1 for 循環
- 3.4.2 while 循環
- 3.4.3 循環的非正常中斷
- 3.4.4 嵌套循環
- 3.5 結構化程序設計
- 3.5.1 程序開發過程
- 3.5.2 結構化程序設計的基本內容
- 3.6 編程案例:如何求 n 個數據的最大值?
- 3.6.1 幾種解題策略
- 3.6.2 經驗總結
- 3.7 Python 布爾表達式用作控制結構*
- 3.8 練習
- 第 4 章 模塊化編程
- 4.1 模塊化編程基本概念
- 4.1.1 模塊化設計概述
- 4.1.2 模塊化編程
- 4.1.3 編程語言對模塊化編程的支持
- 4.2 Python 語言中的函數
- 4.2.1 用函數減少重復代碼 首先看一個簡單的用字符畫一棵樹的程序:
- 4.2.2 用函數改善程序結構
- 4.2.3 用函數增強程序的通用性
- 4.2.4 小結:函數的定義與調用
- 4.2.5 變量的作用域
- 4.2.6 函數的返回值
- 4.3 自頂向下設計
- 4.3.1 頂層設計
- 4.3.2 第二層設計
- 4.3.3 第三層設計
- 4.3.4 第四層設計
- 4.3.5 自底向上實現與單元測試
- 4.3.6 開發過程小結
- 4.4 Python 模塊*
- 4.4.1 模塊的創建和使用
- 4.4.2 Python 程序架構
- 4.4.3 標準庫模塊
- 4.4.4 模塊的有條件執行
- 4.5 練習
- 第 5 章 圖形編程
- 5.1 概述
- 5.1.1 計算可視化
- 5.1.2 圖形是復雜數據
- 5.1.3 用對象表示復雜數據
- 5.2 Tkinter 圖形編程
- 5.2.1 導入模塊及創建根窗口
- 5.2.2 創建畫布
- 5.2.3 在畫布上繪圖
- 5.2.4 圖形的事件處理
- 5.3 編程案例
- 5.3.1 統計圖表
- 5.3.2 計算機動畫
- 5.4 軟件的層次化設計:一個案例
- 5.4.1 層次化體系結構
- 5.4.2 案例:圖形庫 graphics
- 5.4.3 graphics 與面向對象
- 5.5 練習
- 第 6 章 大量數據的表示和處理
- 6.1 概述
- 6.2 有序的數據集合體
- 6.2.1 字符串
- 6.2.2 列表
- 6.2.3 元組
- 6.3 無序的數據集合體
- 6.3.1 集合
- 6.3.2 字典
- 6.4 文件
- 6.4.1 文件的基本概念
- 6.4.2 文件操作
- 6.4.3 編程案例:文本文件分析
- 6.4.4 緩沖
- 6.4.5 二進制文件與隨機存取*
- 6.5 幾種高級數據結構*
- 6.5.1 鏈表
- 6.5.2 堆棧
- 6.5.3 隊列
- 6.6 練習
- 第 7 章 面向對象思想與編程
- 7.1 數據與操作:兩種觀點
- 7.1.1 面向過程觀點
- 7.1.2 面向對象觀點
- 7.1.3 類是類型概念的發展
- 7.2 面向對象編程
- 7.2.1 類的定義
- 7.2.2 對象的創建
- 7.2.3 對象方法的調用
- 7.2.4 編程實例:模擬炮彈飛行
- 7.2.5 類與模塊化
- 7.2.6 對象的集合體
- 7.3 超類與子類*
- 7.3.1 繼承
- 7.3.2 覆寫
- 7.3.3 多態性
- 7.4 面向對象設計*
- 7.5 練習
- 第 8 章 圖形用戶界面
- 8.1 圖形用戶界面概述
- 8.1.1 程序的用戶界面
- 8.1.2 圖形界面的組成
- 8.1.3 事件驅動
- 8.2 GUI 編程
- 8.2.1 UI 編程概述
- 8.2.2 初識 Tkinter
- 8.2.3 常見 GUI 構件的用法
- 8.2.4 布局
- 8.2.5 對話框*
- 8.3 Tkinter 事件驅動編程
- 8.3.1 事件和事件對象
- 8.3.2 事件處理
- 8.4 模型-視圖設計方法
- 8.4.1 將 GUI 應用程序封裝成對象
- 8.4.2 模型與視圖
- 8.4.3 編程案例:匯率換算器
- 8.5 練習
- 第 9 章 模擬與并發
- 9.1 模擬
- 9.1.1 計算機建模
- 9.1.2 隨機問題的建模與模擬
- 9.1.3 編程案例:乒乓球比賽模擬
- 9.2 原型法
- 9.3 并行計算*
- 9.3.1 串行、并發與并行
- 9.3.2 進程與線程
- 9.3.3 多線程編程的應用
- 9.3.4 Python 多線程編程
- 9.3.5 小結
- 9.4 練習
- 第 10 章 算法設計和分析
- 10.1 枚舉法
- 10.2 遞歸
- 10.3 分治法
- 10.4 貪心法
- 10.5 算法分析
- 10.5.1 算法復雜度
- 10.5.2 算法分析實例
- 10.6 不可計算的問題
- 10.7 練習
- 第 11 章 計算+X
- 11.1 計算數學
- 11.2 生物信息學
- 11.3 計算物理學
- 11.4 計算化學
- 11.5 計算經濟學
- 11.6 練習
- 附錄
- 1 Python 異常處理參考
- 2 Tkinter 畫布方法
- 3 Tkinter 編程參考
- 3.1 構件屬性值的設置
- 3.2 構件的標準屬性
- 3.3 各種構件的屬性
- 3.4 對話框
- 3.5 事件
- 參考文獻