遞迴分析與河內塔 江銘輝 五夢網
一、 河內塔問題（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。