用程式碼角度談河內塔(Hannoi)

河內塔一直是個經典範例，在資料結構與演算法的相關課程中幾乎是固定班底。本文從「程式碼」開始說起，有些人知道這種問題可以使用遞迴(Recursive)來解，隨手Google一下也都有多種程式語言所實踐的例子，今天直接由程式碼起步，說明原理，希望透過這種方式可幫助大家更易理解。

閱讀前最好要具備的知識：

1. 河內塔是什麼，本文不再重述，請Google一下。
2. 參數傳遞與存取，你必須能夠辨別目前存取的變數是在哪裡傳進去的。
3. 遞回與推疊之間的關係。

河內塔關鍵演算

這邊以Java語言為例，變數宣告建議用小寫，只是本文會反覆提到ABC三個字母，為了閱讀方便以大寫標示。

public void move(int n, char A, char B, char C) {
    if (n > 0){
        move(n-1, A, C, B);
        System.out.println("將第" + n + "個盤子由" + A + " 移至 " + C );
        move(n-1, B, A, C);
    }
}

有什麼方法可以快速容易理解這段程式呢？其實不用想太多，觀察一下可以發現傳入的參數A B C進行了一些奇怪的置換，遞迴呼叫時一下是A C B，一下又是B A C。

其實這種交換只是為了迎合描述當初歸納的規則(後面再提)，有看到System.out.println( )嗎？它抓取變數A與C，並套入其他字詞顯示盤子如何移動。因此，在A B C三者中，請先關注A與C位置 (即第一、第三個位置，中間先不理他)，目的是要讓輸出的語句能夠符合規則。

不同個數的河內塔

程式碼看完了，接著要理解規則，先考慮三種情況：

1. 只有一個盤子：直接由A柱 → C柱。

2. 兩個盤子：A柱 → B柱，A柱 → C柱，B柱 → C柱。

3. 三個盤子：太長了，直接看圖。

若暫時不看最大的盤子(藍色)，是否就相似「兩個盤子」的情況呢？我們針對「兩個盤子」的情況，用最白話的方式來描述盤子是如何移動的：

1. 把A柱上的小盤子，移到B柱。 (A→B)
2. 把A柱上的中盤子，移到C柱。 (A→C)
3. 把B柱上的小盤子，移到C柱。 (B→C)

到這邊，再回頭看看程式碼，是否可以發現：

move(n-1, A, C, B);
System.out.println("將第" + n + "個盤子由" + A + " 移至 " + C );
move(n-1, B, A, C);

1. 第一行：move呼叫傳入的參數是「A」、「C」、「B」。
2. 第二行：直接print出第一個變數 → 第三個變數的語句。
3. 第三行：move呼叫傳入的參數是「B」、「A」、「C」。

這時冷靜一下，想想第一次呼叫 (也就是在外面，例如在main裡面呼叫) move時，傳入的是按照順序的A B C。所以，第二行的print會抓到誰呢？第一個變數是A，第三個變數是C，於是印出「A → C」，但是這行不會馬上印出來，因為在print前還有一個move呼叫！現在回來看看第一行，第一個傳入A，第三個傳入B，可預期的它會印出「A → B」。同理，第三行，第一個傳入B，第三個傳入C，預期會印出「B → C」。看到這邊，你可以發現，這剛好滿足了前面分析的規則順序，即A→B，A→C，B→C。

再來談談「遞迴」，你可以發現move裡面有move，這種自己呼叫自己的行為就是遞迴了，但是一路呼叫沒完沒了，所以要加個條件讓它能有「停下來的機會」，於是有個 n > 0的判斷式，隨著每次呼叫move時傳入的 n – 1，可預期未來會碰上n = 0的情況，從而使遞迴呼叫結束。

最後我們要把這一切串起來！把頭腦當成電腦，開始執行程式吧，還是以「兩個盤子」為例：

1. move被呼叫了，第一次傳進去的參數是A B C。
2. 第一行又呼叫了一次move，傳入了A C B (就是把step 1傳入的順序交換一下再傳給下個move)、同時也把 n - 1後傳入。
3. 注意，現在人在第2個move裡了，嗯？你說第1個move跑去哪了嗎？請暫且忽略它，記得你目前在遞迴，先不要去管第1個move，你只需要一直執行下去。檢查n是否 > 0，若是，再呼叫一次move (第3次)，又傳入n – 1與交換過的順序的3個參數。
4. 現在人在第3個move裡了……

以下請靠想像，再寫下去你看得更亂。你需要知道的重點是，在move裡面，只有System.out.println( )會輸出結果，因此無論傳入的參數怎麼換，它就只會印出第1個 →  第3個這種描述。

那前面被我們無視的「第1次move」呢？現在假設遞回呼叫結束了 (遇上 n = 0)，將開始彈出(pop)堆疊，觸發各次呼叫move裡面的print，print完再呼叫第3行的move，又是一連串的遞迴。

而為何使用 n = 0作為遞回結束的條件呢？n在這邊表示盤子的總數，前面一直舉的例子「兩個盤子」即是n = 2。細心的你可能已經發現，第一次呼叫傳入的n是2，但河內塔不是要先移動最上面的盤子嗎？注意在此是以遞回的方式來求解，想想前面「無視第1次move」時，是不是馬上進入第2次的move呼叫了，第1次move還無法進行print，最後在彈出堆疊時，print的執行順序是反過來的，即n = 1印完，再印n = 2 (n=0被排除了，不會印出東西)。

你也可以用比較直觀的方式思考，假設有3個盤子，要移動大盤子(3)，是不是要先移動中盤子(2)，要移動中盤子(2)，是不是要先移動小盤子(1)，這就是 n – 1的概念。而一路減到最後，移動是最小、最上面的盤子，因為它沒有阻礙了，於是直接A → C，而因為小盤(1)移走了，所以中盤(2)也沒有阻礙了，於是直接A→B，這不就接回我們前面談的步驟了嗎？

其實在仔細想想，你還會發覺在n =2的情況下，第一步是 A → B。在n = 3的情況下，第一步卻是A → C，但演算法都沒有變，一樣都是第一步，為何會有兩種走法？這就是這個演算法的神奇之處，欲知詳細請見後記。

後記

1. 以個人的經驗而言，最通盤的理解方法就是透過紙筆來模擬，把整個堆疊的push與pop動作跑一次，並注意每次呼叫move的傳入參數，了解他們是如何互換順序的。
2. 如果你多試著解4、5、6…n個盤子的問題，可以發現單數盤子第一步是A→C，雙數盤子第一步是A→B，在遞迴呼叫配合ABC交換的情況下，也恰好滿足這種規律。
3. 還是有障礙嗎？那麼該搬出這句名言了：「遞迴只應天上有，凡人應當用迴圈」。