Python求解河内塔问题：递归程序设计艺术(1)

递归程序设计方法(简称递归)是指函数直接或者间接调用自己的现象。递归是一种有趣的程序设计方法，往往区区几行代码就能达到神奇的效果。递归同时是一种非常数学化的方法，很多软件工程师用不好递归，原因就在于没有理解递归的本质。

递归的本质

递归的本质就是数学归纳法。什么是数学归纳法？比如，如果我们要证明前n个奇数的和等于​​​​​​​，例如：1+3+5=，1+3+5+7=，也就是说1+3+……+(2n-1)=。那么怎么证明呢？

第一步，简称为确定归纳边界。当n=1时看看定理是否成立。当然，定理显然是成立的，因为1=。

第二步，称为归纳假设。假设n=k时定理成立。即前k个奇数的和等于。

第三步，称为递归推导，看看n=k+1时定理是否成立。因为1+3+……+(2k-1)+（2(k+1)-1）= ，可见，n=k+1时定理也是成立的。

综合上述，我们认为前n个奇数的和的确等于​​​​​​​，这就是数学归纳法。递归实际上也是按照这三步来的，分别简称为确定递归边界、递归假设和递归推导。不同之处仅仅在于，数学归纳法试图证明一个定理成立，而递归的目的是根据输入生成输出。

下面我们通过例子来说明如何正确地使用递归。

河内塔问题

递归程序的一个著名例子就是Hanoi塔（中文翻译为河内塔或汉诺塔）问题。

有三根插在地上的杆子A、B、C。A杆上套有n个中间有孔的碟子，碟子的直径从上到下分别是1、2、……、n（参见上图）。现在我们试图把所有碟子从A杆移到C杆，条件是：

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三个参数，分别表示来源、中转和目的地。注意，a、b、c的初值分别是字符串"A"、"B"和"C"。

确定了输入和输出之后，下面按照递归的三个步骤解决Hanoi塔问题。

第一步，确定递归边界。所谓递归边界就是输入参数要满足的一个条件，在这个条件下，原问题可以很容易得到解决。河内塔问题在什么情况下最容易解决？显然，当输入参数n=1时，问题最好解决。因为此时a上仅有一个碟子，直接把这个碟子从a移到c即可，这就是递归边界。注意，该递归边界只与n有关，与其他参数无关。

第二步，递归假设。这里可以假设n-1个碟子可以从a、b、c中的任意一个杆子移到另外任意一个杆子上。可能你会问：“怎么才能把n-1个碟子从一个杆子移到另一个杆子上？”这个问题不用回答，因为它是假设成立的。编程序也可以假设？是的，可以假设，这正是递归程序设计神奇而有魅力的地方。

关于递归假设，你要注意两点：第一，递归假设时所用到的参数应该比原问题的参数更靠近边界。比如上面分析中，n-1就比n更靠近边界；第二，参数的个数、每个参数的类型和作用都应该与原参数一一对应。违反了这两点中的任何一点都会导致递归的失败。这是因为，递归的本质是把一个问题转化为一个规模更小一点的问题解决。所谓规模小，表现在函数参数上，就是指比原参数更靠近边界。如果相反操作，就会导致问题离边界越来越远，最终导致递归陷入死循环，问题求解失败。

n-1个碟子先从A杆移到B杆 

第三步，递归推导。就是利用河内塔问题在n-1个碟子上的解来推导问题在n个碟子上的解。既然n-1个碟子可以从任意一个杆子移到另外任意一个杆子上，那么我们可以这样移：以c作为中转，先把a最上面的n-1个碟子移到b杆上（参见上图），然后再把a杆剩下的直径为n的那个碟子直接移到c杆上（参见下图）。

最后把b上的n-1个碟子移到c上（参见下图）。这样问题就得到了解决。

递归程序设计的原则就是：首先用一个if语句判断当前满不满足递归边界条件。如果满足就按递归边界处理，否则利用递归假设和递归推导进行编程即可。河内塔问题的递归程序如下所示：

解决河内塔问题的Python递归程序

从本质上讲，递归程序设计方法仍然是一种自顶向下的程序设计方法。因为主程序调用的子程序就是主程序自己。唯一区别在于一般自顶向下调用时不用考虑是否更靠近边界，而递归调用必须要考虑这个问题。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！