递归分析与河内塔 江铭辉 五梦网
一、 河内塔问题（Towers of Hanoi Problem）
古印度有一个很有趣的传说，在伯那尔斯(Benares)的一座大寺庙里，有一栋被称为是世界之中心点的楼阁，它的下面有一块黄铜制的方形盘子，盘子上竖立着三根钻石制成的棒子。在开天辟地的时候，万能的上帝波罗摩（Brahma）在其中一根钻石捧上放置了六十四个大小都不相同的金圈，这些金圈是依大在下小在上顺序地迭放着，叫河内塔。古印度人也称它为梵天培（Towers of Brahma）。上帝所颁下的意旨，是要庙里的婆罗门和尚们将这六十四个金圈移到另一根钻石棒上，不过，在移动这些金圈时，有两项规则：第一是每一次只能移动一个金圈；第二是在移动的过程中，较大的金圈不能放在较小的金圈上。（图）
图：传说河内塔问题如果解决，全世界就会毁灭
当这件工作完成后，也就是说，这六十四个金圈都已按照上面两项规则移到另一根钻石棒后，这个梵天塔寺庙就一切都会化为灰烬，接着将会是一声晴天霹雳，然后，整个世界就会消失了。
若传说中的确有其事，生活在地球的人们有一天，伯那尔斯(Benares)寺的和尚，完成上帝的指示，全世界的人岂不都完蛋。
让我们算算看这件事会不会发生，下面我们将会证明，根据那两项原则，同时，婆罗门教徒在搬动金圈的过程中，所有的步骤都遵守那二大原则没有错误，那么，他们所需要搬动的次数共需264－1次，即18,446,744,073,709,551,615次。如果这些和尚们没有片刻休
息地每秒钟搬动一次，那么，他们要完成这件工作所需的时间超过5840亿年。这个惊人的数字实在很大，所以，读者们，不要杞人忧天，放心地上床睡觉吧!
二、 递归分析
1.数列：
我们如何算出婆罗门教的僧侣们依天帝的指示来完河内塔游戏，总共需移动264－1次呢？要解决这个问题非借重数学上的递归分析不可，首先我们介绍数列。
读者都非常熟悉下面的一组等差级数：
1、2、3………n………
设a1＝1、a2＝2、a3＝3、………an＝n………
这个数列我们可以用下列数列来表示，即：
a1＝1、a2＝a2－1＋1、a3＝a3－1＋1、………、an＝an －1＋1………
在举一个等比级数的例子，如下：
21、22、23、………2n、………
设：
a1＝21、a2＝22 、a3＝23………an＝2n、………
我们亦可以这样表示，即：
a1＝21、a2＝22－1×2 ＝2 a1、a3＝23－1×2＝2 a2………an＝2n－1×2＝2 an－1
2.递归律的定义
所谓递归律是指：
假设一个数列a1、a2、a3………an………，对于任意n，an可以用一个或多个ai的式子来表示（i小于n），称为递归律，如1、2、3………n………的等差级数，an可以用an －1＋1来表示，21、22、23、………2n、………的等比级数，an可以用2 an－1来表示。至于费波那契级数（0、1、1、2、3、5、8、13、21、34……），an可以用an －1＋an －2来表示。
三、 河内塔问题的解决
了解递归律后，我们就用它来算出河内塔问题及所需次数。
我们先从只有一个金圈开始着手：
假设三根钻石棒分别为A、B、C棒，并假设金圈开始时，放在A棒上，现在要搬到C棒上，同时金圈由小至大依序编以1、2、3……64的号码。
1. 如果金圈只有一个，则将它从A棒搬到C棒，只需搬动一次，我们记为a1＝1；如图1a（刚开始）、图1b（从A棒搬到C棒）。
图1a：刚开始
图1b：从A棒搬到C棒
图1：金圈只有一个，则将它从A棒搬到C棒，只需搬动一次。
2. 如果金圈有二个，则我们需要依下列顺序来搬动3次搬动，才能得到所希望的结果（如图2a：刚开始、2c、2d），我们记为a2＝3：
（1）将1号金圈由A棒搬到B棒（图2b）
（2）将2号金圈由A棒搬到C棒（图2c）；
（3）将1号金圈由B棒搬到C棒（图2d）；
图2a：刚开始
图2b：将1号金圈由A棒搬到B棒
图2c：将2号金圈由A棒搬到C棒
图2d：将1号金圈由B棒搬到C棒
图2：金圈有二个，则将它从A棒搬到C棒，要三次。
3. 如果金圈共有三个，则搬动次数就会增加，我们将各个步骤列出如下，总共搬了7次，我们记为a3＝7：
（1） 将1号金圈由A棒搬到C棒（图3b）
（2） 将2号金圈由A棒搬到B棒（图3c）
（3） 将1号金圈由C棒搬到B棒（图3d）
（4） 将3号金圈由A棒搬到C棒（图3e）
（5） 将1号金圈由B棒搬到A棒（图3f）
（6） 将2号金圈由B棒搬到C棒（图3g）
（7） 将1号金圈由A棒搬到C棒（图3h）
图3a：刚开始三个金圈全部放在A棒
图3b：将1号金圈由A棒搬到C棒
图3c：将2号金圈由A棒搬到B棒
图3d：将1号金圈由C棒搬到B棒
图3e：将3号金圈由A棒搬到C棒
图3f：将1号金圈由B棒搬到A棒
图3g：将2号金圈由B棒搬到C棒
图3h：将1号金圈由A棒搬到C棒
图3：金圈有三个，则将它从A棒搬到C棒，要七次。
如此我们就得到我们所希望的结果。因此总共要搬动7次。即a3＝23－1＝7
从上面有关三个金圈的讨论，我们可以猜到64金圈的搬动，势必大费周章，将它们逐步搬动并加以记录，是件麻烦的事，像这样问题，递归分析及递归律的威力，就显现出来。使用这个方法时，我们不必再局限于64这个数字，而假定A棒的金圈共有n个，并以an，表示将这n个金圈由A棒搬移到C棒所需的次数。因为在搬移工作完成的时候，第n号金圈必须从A棒的最下面搬移到C棒的最下面;而完成搬动之前，A棒上必须只剩下第n号金圈而C捧上则须是一个金圈都没有；换言之，在将第n号金圈由A棒移到C捧之前，前面那n－1个较小的金圈必须按顺序地迭放在B上时，才将第n个金圈由A棒搬移到C棒，在完成神明的指示，将64个金圈由A棒搬移到C棒，我们的构想如下：
（1） 将1至n－1号等n－1个金圈由A棒移到B棒（如图4ｂ）；
（2） 将第n个金圈由A棒移到C棒; （如图4ｃ）
（3） 将1至n－1号等n－1个金圈由B棒移到C棒（如图4ｄ）。
图４ａ：刚开始ｎ个金圈全部放在A棒
图4ｂ：将1至n－1号等n－1个金圈由A棒移到B棒（即an－1次）
图4ｃ：将第n个金圈由A棒移到C棒（只需搬动一次）
图4ｄ：将1至n－1号等n－1个金圈由B棒移到C棒（即an－1次）
图４：将n个金圈由A棒移到C棒的步骤。
完成（1）的步骤，需an－1步，完成（２）的步骤仅需１步，完成（３）的步骤，需an－1步。
因此，将n个金圈由A棒搬移到C棒所需的次数等于2 an－1＋1。亦即，
an＝2an－1＋1
因此：
a0＝0（没有金圈，无需搬动），a1＝1（只有一个金圈，只需搬动一次），a２＝３（只有二个金圈，只需搬动三次），a３＝７（只有三个金圈，只需搬动七次）
接下来是：a4＝15，a5＝31，a６＝６3，a７＝１２７，……an＝2an－1＋1
即a2＝22－1，a3＝23－1，a4＝24－1，a5＝25－1，a６＝2６－1，a７＝2７－1，…………an＝2n－1
因此若有64个金圈，则：
A64＝264－1＝18,446,744,073,709,551,615。