1.2 递归程序设计
上一节简单介绍了自顶向下、先整体后局部的程序设计方法，接下来讲解递归程序设计。递归是指函数自己调用自己的程序设计方法。有意思的是：递归是自顶向下的特殊情形。一般的自顶向下是指一个函数对另一个函数的调用，而递归是指函数对自己的调用。
我们认为，递归的实质是数学归纳法。什么是数学归纳法？例如，如果要证明前n个奇数的和等于n2，如1+3+5＝32，1+3+5+7＝42，也就是说1+3+…+（2n－1）＝n2，那么怎么证明呢？
第一步，称为归纳边界。即当n＝1时看看定理是否成立。当然，定理是成立的，因为1＝12。
第二步，称为归纳假设。假设n＝k时定理成立，即前k个奇数的和等于k2。
第三步，称为递归推导。看看n＝k+1时定理是否成立。因为1+3+…+（2k－1）+［2（k+1）－1］＝k2+2k+1＝（k+1）2，可见，n＝k+1时定理是成立的。
综合上述三步，我们认为前n个奇数的和的确等于n2，这就是数学归纳法。递归实际上也是按照这三步来的，分别称为递归边界、递归假设和递归推导。不同的地方仅仅在于，数学归纳法是试图证明一个定理成立，而递归的目的是根据输入生成输出。
下面通过例子来说明为什么递归的实质是数学归纳法。
1.2.1 河内塔问题
递归程序的一个著名例子就是河内塔（Hanoi塔，也译为汉诺塔）问题。
有3根插在地上的杆子A、B、C。A杆上套有n个中间有孔的碟子，碟子的直径从上到下分别是1，2，…，n，如图1－1所示。现在我们试图把所有碟子从A杆移到C杆，条件是：
图1－1 河内塔问题
1）任意一根杆子上只有最上面的碟子可以移动。
2）任何情况下，大碟子都不能放在小碟子的上面。
3）B杆可以作为中转用。
例如，当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。这个想法是错误的，因为我们并不清楚这n个碟子在哪根杆子上。所以输入参数除了n之外，应该还有a、b、c 3个参数，分别表示“来源”“中转”“目的地”。注意，a、b、c的初值分别是“A”“B”“C”。
确定了输入和输出之后，就可以按照递归的方法解决这个问题了。既然递归的实质是数学归纳法，并且数学归纳法是按照3个步骤进行思考的，那么与之对应，递归也应该按照3个步骤进行思考。
第一步，递归边界（对应于数学归纳法的归纳边界）。所谓递归边界就是输入参数要满足的一个条件，在这个条件下，原问题可以很容易得到解决。确定河内塔问题的边界在哪里，就是确定输入参数在什么情况下，问题可以很容易得到解决。显然，当输入参数n＝1时，问题最好解决，因为此时a上仅有一个碟子，直接把这个碟子从a移到c即可。
第二步，递归假设（对应于数学归纳法的归纳假设）。即假设n－1个碟子可以从a、b、c中的任意一根杆子移到另外任意一根杆子上。读者可能会有疑问：“我怎么把n－1个碟子从一根杆子移到另一根杆子上？”。这是假设的。编程序也可以假设？是的，可以假设，这正是递归程序设计神奇又有魅力的地方。
关于递归假设，需要注意两点：第一，递归假设时所用到的参数应该比原问题的参数更靠近边界（递归边界的简称，以下同），例如上面的分析中，n－1就比n更靠近边界；第二，参数的个数、每个参数的类型和作用都应该与原参数一一对应。违反了这两点中的任何一点都会导致递归的失败。
第三步，递归推导（对应于数学归纳法的归纳推导）。就是利用河内塔问题在n－1位置处的解来推导问题在n处的解。既然n－1个碟子可以从任意一根杆子移到另外任意一根杆子上，那么我们可以这样移：以c作为中转，先把a最上面的n－1个碟子移到b杆上，如图1－2所示，注意a、b、c的初值分别是“A”“B”“C”（后同）；再把a杆剩下的直径为n的那个碟子移到c杆上，如图1－3所示；最后把b杆上的n－1个碟子移到c杆上，如图1－4所示，这样问题就得到了解决。
图1－2 n－1个碟子先从A杆移到B杆
图1－3 最大的碟子从A杆直接移到C杆
图1－4 n－1个碟子再从B杆移到C杆
递归程序设计的原则就是：首先用一个if语句判断当前参数是不是处于递归边界。如果是，就按递归边界处理；否则，利用递归假设和递归推导进行编程即可。解决河内塔问题的递归程序如下：
从本质上讲，递归程序设计方法仍然是一种自顶向下的程序设计。在编写一个递归程序的函数体时，被调用的子函数就是正在被实现的函数本身。既然子程序都可以先调用后定义，那么递归子程序当然也是可以先调用后定义的。唯一区别就是一般自顶向下调用的是其他函数，而递归调用的是当前这个函数本身。
1.2.2 兔子问题
一对刚出生的小兔子两个月后就能生下一对小兔子，且之后的每个月都能生一对小兔子。刚生下的小兔子过两个月以后也能每个月生一对小兔子，以此类推。假设兔子永远不会“翘辫子”，现在给你一对刚出生的小兔子，问n个月后有几对兔子？
显然，输入参数是n。递归边界是n＝0或n＝1，此时小兔子还没有出生，所以兔子数目都是1对。递归假设也很好做。下面考虑递归推导。当n＞2时，每个月的兔子由上个月的兔子和本月新出生的兔子组成。而本月新出生的兔子数与两个月前的兔子总数相同，因为那时即使是刚出生的兔子现在也能在本月生出一对新的小兔子。所以，本题的解就是著名的斐波那契（Fibonacci）数列：
运行结果如下：
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 字符串匹配问题
如果说上节的兔子问题还可以用非递归的方法实现，那么下面这个问题就很难用非递归方法来实现了。
假设“∗”可以匹配0个或0个以上的字符，“？”可以匹配且仅匹配一个字符。请写一个递归函数match（ pattern，str），判断字符串str是否与模式pattern匹配。
例如，在操作系统里寻找一个文件时，不必写全文件的名字，可以使用“∗”和“？”这两个通配符。如AB∗C？.doc表示任何以AB打头、倒数第二个字符是C的doc文档。
我们仍然按照递归程序三部曲来考虑这个函数。
第一，递归边界。在什么情况下可以直接判断str是否与pattern匹配？显然，如果str是个空字符串（即长度为0的字符串），那pattern也必须是个空字符串两者才能匹配。反之，如果pattern是个空字符串，那它也只能和空字符串匹配。所以这个边界条件是str或pattern为空字符串。
第二，递归假设。假设在pattern或者str比原来少一个字符的情况下，match函数总能正确地判定二者是否匹配。注意递归假设所用到的参数要比原参数更靠近边界。
第三，递归推导。我们可以考虑pattern的第一个字符。如果它是“？”，则str的第一个字符可以忽略，只需考虑它们剩下的部分是否匹配即可。如果它是“∗”，则又分为两种情况：“∗”只匹配0个字符，这意味着可以把“∗”删除，然后考虑pattern剩下的部分是否与str匹配即可；“∗”匹配1个或1个以上的字符，此时可以把str的第一个字符删除，然后看它剩下的部分与pattern是否匹配即可。
综上所述，可以给出递归代码如下：
_test_match（）函数的第三个参数是真实结果，我们会把匹配结果也打印出来与它进行对比。运行结果如下：
ababaab，a∗b，True，True
ababaab，∗abab∗，True，True
ababaab，a∗a？b，True，True
ababaab，a∗bb，False，False
ababaab，aabab∗，False，False
ababaab，a∗b？b，False，False
1.2.4 组合问题
从5个不同的小球里任取3个，有多少种取法？这是一个典型的组合问题，答案是C（5，3），即10种。但是我们现在并不是要用数学方法求组合的解，而是要求编写一个递归函数comb（m，n），以求得从m个小球里任取n个的组合数，其中m≥n始终成立。
我们根据递归程序三部曲来考虑这个函数。
第一，递归边界。在什么情况下，组合数可以直接求得，而不必进行递归？显然当n＝0时，不论m等于多少，组合数都是1。把n＝0作为递归边界已经足够了。但是，如果还有其他边界则也应该考虑在内，这样有助于程序在递归过程中更快地接近边界，从而提高程序运行速度，减少内存占用。如果n＝m，则意味着把所有的小球都取出，这样的组合数也只有1个。
第二，递归假设。假设只要把m和n做更接近于边界的变化，则组合数总能求得出来。
第三，递归推导。我们把最后一个小球Z拎出来单独考虑。如果最后取出来的n个小球里不包含Z，则相当于从Z之前的m－1个小球里取n个，根据递归假设，共有comb（m－1，n）种组合。反之，如果取出来的n个小球里包含Z，则相当于从Z之前的m－1个小球里取n－1个，根据递归假设，共有comb（m－1，n－1）种组合。所以递归程序如下：
解决了组合问题，请大家思考：如何解决排列问题？
1.2.5 人字形铁路问题
如图1－5所示，有一段人字形的铁路，火车只能从右边铁路线驶进，并且只能从左边铁路线驶出。驶进来的火车可以停在人字形的上半部分（直线）铁路线上，从而让后进来的火车先从左边铁路线驶出。当然它也可以进来之后不作停留直接驶出。假设右边有n列火车，问从左边驶出的n列火车的排列有多少种？
图1－5 人字形铁路问题：火车只能右边进左边出
例如，假设右边有3列火车A、B、C，则从左边驶出的火车的排列只有5种：ABC、ACB、BAC、BCA和CBA。3列火车的所有6种排列里唯有CAB是不可能的。
显然，本题的输入参数是右边等待进入铁路的火车的数量n。这当然没有错误，可问题是接下来的递归推导会比较困难。为了解决这个难题，我们再增加一个参数m，表示从右边开进铁路，停在堆栈里，没有开出的火车数量。m的初值是0。
显然，递归边界是n＝0。此时，不论停在铁路上的火车（即m）有多少，这些火车都只能按照次序一一从左边输出。所以输出的排列数目都只有一个。
递归假设比较好理解，这里略过不提。对于递归推导，当两个参数分别是n、m时，有两种方法分解问题。第一，右边等待的n列火车中的第一列开进铁路，这时问题参数分别转化为n－1、m+1；第二，停在铁路上的m列火车中的第一列开出，这时问题参数分别转化为n、m－1，前提是m＞0。所以我们分别用这两组参数进行递归调用即可。程序如下：
运行结果如下：
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
这个问题有意思的地方在于，虽然m的值加1了，但是子问题的参数还是比原问题更靠近递归边界。这是因为递归边界仅与参数n有关，与m无关。