汉诺塔问题的两种解法(4)

第四节 汉诺塔问题的递归解法——移动所有盘子

上一节我们实现了连续移动两个盘子（数字），现在我们发挥一点儿想象力，将上一节的两个盘子当作一个盘子来处理，从而得出移动3个盘子的过程，代码如图22所示。

图22 连续移动三个盘子（数字）的过程

我们还可以写出连续移动4个盘子的过程，代码如图23的左图所示。在暂停按钮的点击事件中调用该过程，即可执行移动操作。读者不妨测试一下，看看虚实。

图23 连续移动4个盘子的过程

以此类推，我们可以编写出连续移动任意多个盘子的过程，如果盘子数为N，那么连续移动N个盘子的过程，要依赖于移动前N-1个盘子的过程。像这样，对N个对象的操作要依赖于对前N-1个对象的操作，解决这样的问题，需要用到一种叫做“递归”的编程方法，即，在一个过程内部调用这个过程本身。下面我们编写移动N个盘子的过程——移动N，代码如图24所示。

图24 连续移动N个盘子的过程

上述过程里增加了一个参数N，这是至关重要的一步，它的作用有两点：一是借助于N，我们得以描述数量相邻的两组盘子之间的移动规律，也就是在N与N-1之间建立联系，如图24中条件语句中的“否则”分支部分；二是为递归调用提供了一个出口，即当N=0时，退出递归，执行条件语句的“则”分支。为递归程序设置出口，这是使用递归方法的第一要务，否则，程序有可能进入死循环。

在暂停按钮的点击事件中调用移动N过程，参数N为左列表的长度，代码如图25所示。

图25 连续移动N个数字

在测试手机上的输入框中输入数字10，然后点击开始按钮，之后再点击暂停按钮，程序的运行结果如图26所示。

图26 测试：连续移动10个数字

这次测试在我的手机上运行了很长时间，我很好奇究竟用了几秒钟，5秒？10秒？还是用程序来测一下吧，代码如图27所示，测试结果如图28所示，竟然耗时24秒！

图27 测量运算时长

图28 运算时长的测试结果——24秒钟

前面提到过移动次数与盘子数n之间的关系，移动次数 =

，当n=10时，次数=1023。如果仅仅是1023次四则运算，用时不会超过1秒钟，但是当涉及到列表的操作时（添加、删除列表项），运算量呈几何级数增长，况且递归调用过程中，消耗大量内存来保存局部变量——过程的参数，由此导致的资源及运算力的消耗都是巨大的。

程序写到这里，已经实现了解决汉诺塔问题的目标，不过，心中总有些不甘，希望能够将数字移动的过程呈现出来，于是有了后面的几节。

== 未完待续 ==