8-10　河内塔问题

学习计算机程序语言，碰上递归式调用时，最典型的应用是河内塔（Tower of Hanoi）问题，这是由法国数学家爱德华·卢卡斯（François Édouard Anatole Lucas）提出的问题。

问题内容是有3根柱子，可以定义为A、B、C，在A柱子上有n个穿孔的圆盘，盘的尺寸由下到上依次变小，它的移动规则如下。

（1）每次只能移动一个圆盘。

（2）只能移动最上方的圆盘。

（3）必须保持小的圆盘在大的圆盘上方。

只要保持上述规则，圆盘可以移动至任何其他两根柱子。

移动结果将如下所示。

相传古印度有座寺院内有3根柱子，其中A柱子上有64个金盘，僧侣间有一个古老的预言，如果遵照以上规则移动盘子，当盘子移动结束后，世界末日就会降临。假设我们想将这64个金盘从A柱子搬到C柱子，其实可以将问题拆解如下。

（1）借用C柱子当暂时移动区，然后将63个盘子由A柱子移动到B柱子。

（2）将最大的圆盘由A移动到C。

（3）将B柱子上的63个盘子移动到C。

上述是以印度古寺院的64个圆盘为实例说明，可以应用于任何数量的圆盘。其实分析上述方法可以发现已经有递归调用的样子了，因为在拆解的方法3中，圆盘数量已经少了一个，相当于整个问题变小了。

假设圆盘有N个，这个题目每次圆盘移动的次数是2N-1次，一般真实玩具中N是8，将需移动255次。如果依照古代僧侣所述的64个圆盘，需要2⁶⁴-1次，如果移动一次要1秒，这个数字约是5845.54亿年，依照宇宙大爆炸理论估算，目前宇宙年龄约137亿年。

程序实例ch8_24.java：以递归式调用处理河内塔问题。

执行结果

上述程序的重点是第3～14行的hannoi()方法，这个方法的重点是先看看是否是只剩下一个圆盘，如果是则将圆盘移至C，否则将最大圆盘上方所有的圆盘搬走，然后将最大圆盘搬到C，遵循以上原则做递归式调用。最后读者须留意，第5、6行和10、11行说明了圆盘的移动方式。