【筆記】河內塔 - 用Java實作

河內塔的問題是用來學習遞迴（Recursion），之前看了很多例子，寫法都大同小意，前陣子就自己也依樣畫葫蘆，並把註解寫在程式碼中，用意是讓自己可以一目瞭然，若你也曾被這樣的程式碼感到困惑過，希望這個例子可以讓你更明白。

package idv.jk.tryit.algorithm;

public class TowerOfHanoi {
    /**
     * 河內塔實作。在第一根柱子上的n個盤子，搬到第三根柱子上。規則：
     * 1. 一次搬一個盤子
     * 2. 搬運過程中大盤子必需在小盤子之下
     *
     * @param numberOfDisks 要移動的盤子數目
     * @param beginning     盤子的開始位置所在的柱子
     * @param auxiliary     移動過程中做為輔助暫放盤子用的柱子
     * @param destination   盤子的目的地位置所在的柱子
     */
    public void move(int numberOfDisks, 
                        String beginning, 
                        String auxiliary, 
                        String destination) {
        if (numberOfDisks == 1) {
            //遞迴的重點之一在於要有結束條件，就是當條件符合時，
            //就不會再呼叫自身的這個方法（method）
            System.out.println(String.format("Moving disk from %s to %s", 
                                                beginning, 
                                                destination));
        } else {
            
            //第一步，先把 n - 1 塊盤子從第一根柱子(beginning)搬到第二根柱子，
            //此時, 需要使用第三根柱子當做輔助。
            //所以最上面傳進來的 auxiliary 參數當成目的地的柱子, 
            //最上面傳進來的 destination 參數當成輔助的柱子。

            //下面這一行執行完後，在第一根柱子上，除了最下面的盤子以外的盤子，
            //都會被搬到第二根柱子上。
            move(numberOfDisks - 1, beginning, destination, auxiliary);

            
            //第二步，再把第一根柱子上剩下的最下面的盤子從第一根柱子搬到第三根柱子上。
            move(1, beginning, auxiliary, destination);

            //第三步，再把現在在第二根子上 n - 1 塊盤子從第二根柱子搬到第三根柱子，
            //此時, 需要使用第一根柱子當做輔助。
            //所以最上面傳進來的 auxiliary 參數當成開始的柱子, 
            //最上面傳進來的 beginning 參數當成輔助的柱子。
            move(numberOfDisks - 1, auxiliary, beginning, destination);
        }
    }

    public static void main(final String[] argv) {
        /*
            第一根柱子標註為 A，
            第二根柱子標註為 B，
            第三根柱子標註為 C。
            現在要從 A 柱上的 3 個盤子搬到 C 柱上
         */
        new TowerOfHanoi().move(3, "A", "B", "C");
    }
}