## 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 塔问题。 最后对递归方法做个小结。 递归是非常重要的算法设计方法，在解决很多具有递归性质的问题、结构的时候，设计 递归算法往往是直接而简单的。递归定义必须满足以下条件才是良定义的： + 有一个或多个无需递归的奠基情形； + 递归总是针对规模更小的问题。 有了这两个条件，递归链最终将到达奠基情形，从而使递归过程终止。 虽然递归算法容易设计、实现，也容易理解，但递归是有代价的。由于递归涉及大量的 函数调用，因此需要耗费较多的内存和较长的执行时间，即递归算法的效率较差。而迭代算 法不涉及函数调用，故速度更快，更节省内存。