【Java】ハノイの塔2

再帰処理を利用してハノイの塔の解法を解説したいと思います。
が、しかし、その前に再帰処理について解説したいと思います。

再帰処理を理解するコツ

そもそもの「再帰処理とは」を考える前に、再帰処理を理解するコツを紹介します。

1. 再帰処理を理解する上で大切なのは、途中経過はブラックボックスのままでよく、イメージを掴むことです。重要なのは、どのような処理を繰り返したいのかを考えることです。
2. 途中経過がブラックボックスのままでよいのは、再帰処理はfor文のようなループ処理とは異なり、制御変数の変化を考えて処理の流れを直接追うことが難しいからです。従って、従来のループ処理とは異なる考え方が必要になります。
3. 再帰処理のメリットは、処理をスマートに記述することができるという点です。つまり、人間の大まかな考えをそのままプログラムに置き換えることができます。細かい処理を考える必要はありません。
4. 完璧な理解を得るために深く考えるのではなく、大まかな処理のイメージを大事にしてください。

以上を踏まえた上で解説を進めていきます。

再帰処理とは

再帰処理とは、メソッド等が自分自身を呼び出すこと（ここでは、定義したhanoiメソッドの処理内容としてhanoiメソッドを呼び出すこと）を指します。 とりあえずは、ここまでをしっかり覚えてください。 下記の内容は、イメージを掴むだけで良いです。
また、再帰処理は、同じ問題をより小さい部分に分割し、その解法を再帰的に適用する方法です。これにより、複雑な問題をより単純な問題に分解し、解決することができます。

ハノイの塔2のコード

従前の「ハノイの塔1のコード」を基礎にして、ハノイの塔を再帰処理を使って解きます。

import java.util.*;

class Main {
    /*
    piles   :  3本の杭をListに格納
    名前なし :  杭は、LinkedList。円盤を格納
    名前なし :  円盤は、円盤の大きさを整数で表す。 ex. 4 3 2 1
    */

    static List<LinkedList<Integer>> piles;

    static void initialize(int n) {
        piles = new LinkedList<>();

        for (int i=0; i<3; i++)
            piles.add(new LinkedList<>());

        for (int i=n; i>=1; i--)
            piles.get(0).add(i);
    }

    static void printPiles() {
        System.out.println("--");
        
        for (int i=0; i<3; i++) {
            System.out.print(i + ":");
            for (int disk : piles.get(i))
                System.out.print(" " + disk);

            System.out.println();
        }
    }

    // 円盤を動かすメソッド
    static void moveOne(int from, int dest) {
        int disk = piles.get(from).removeLast();
        piles.get(dest).add(disk);
    }

    // 再帰処理
    static void hanoi(int n, int from, int dest, int work) {
        if (n == 0) {
            return;
        }
        hanoi(n-1, from, work, dest);
        moveOne(from, dest);
        printPiles();
        hanoi(n-1, work, dest, from);
    }

    public static void main(String args[] ) {
        int n = 3;
        System.out.println(n);

        initialize(n);
        printPiles();

        // 再帰処理の呼び出し
        hanoi(n, 0, 2, 1);
    }
}

ハノイの塔1のコードから書き加えたのは、コメントを付けた 「円盤を動かすメソッド」・「再帰処理」・「再帰処理の呼び出し」 の3箇所です。

---

再帰処理の呼び出しの解説

hanoi(n, 0, 2, 1);

hanoiメソッドを呼び出し、第一引数で変数nを、第二引数で0を、第三引数で2、第四引数で1を渡します。

この呼び出しは、実は、n枚の円盤を0番目の杭から2番目の杭へ移動させます。（1番目の杭を経由します。）という命令を出しています。

---

円盤を動かすメソッドの解説

static void moveOne(int from, int dest) {
    int disk = piles.get(from).removeLast();
    piles.get(dest).add(disk);
}

1. 仮引数としてfromとdestを受け取るmoveOneメソッドを定義して、
2. from番目の杭の最後の要素（＝円盤）を削除して、その要素を変数diskに代入します。
3. dest番目の杭に、変数diskに代入された要素（＝円盤）を加えます。

moveOneメソッドは、再帰処理の中で呼び出すので、杭を表す変数fromとdest・円盤を表す変数diskを厳密に追うことはせず、杭にある円盤を移動させるメソッドなんだという大まかなイメージで良いです。

---

再帰処理の解説

まずは再帰処理のコードの解説をする前に、ハノイの塔の手順は下図の通りになります。

上図は、3つのフェーズに分けて考えます。
1. 0回目の状態 → 3回目の状態
2. 3回目の状態 → 4回目の状態
3. 4回目の状態 → 7回目の状態
下記で、各々のフェーズについて解説します。

第1フェーズ：0回目の状態 → 3回目の状態

n-1枚の円盤を0番目の杭から1番目の杭に移動させます。（2番目の杭を経由します。）

第2フェーズ：3回目の状態 → 4回目の状態

一番大きい円盤を0番目の杭から2番目の杭へ移動させます。

第3フェーズ：4回目の状態 → 7回目の状態

n-1枚の円盤を1番目の杭から2番目の杭に移動させます。（0番目の杭を経由します。）

この第1フェーズから第3フェーズまでが再帰処理のコードを書く上での大まかな考えにあたります。これらを踏まえた上で、下記で再帰処理のコードを解説します。

---

再帰処理のコード解説

static void hanoi(int n, int from, int dest, int work) {
    if (n == 0) {
        return;
    }
    hanoi(n-1, from, work, dest);
    moveOne(from, dest);
    printPiles();
    hanoi(n-1, work, dest, from);
}

1. 仮引数としてnとfromとdestとworkを受け取るhanoiメソッドを定義して、
2. n == 0という条件式のif文を定義して、
3. 条件満たしたら、returnにより、この再帰処理のhanoiメソッドを抜け出します。
   （ 2. と 3. 併せて、ベースケースまたは終了条件と言います。）
4. hanoi(n-1, from, work, dest)は第1フェーズです。n-1枚の円盤をform番目の杭からwork番目の杭に移動させます。（dest番目の杭を経由します。）という命令を出しています。
5. moveOne(from, dest)は第2フェーズです。円盤をform番目の杭からdest番目の杭に移動させます。
6. 円盤を移動させた後の状態をprintPilesメソッドで標準出力に出力します。
7. hanoi(n-1, work, dest, from)は第3フェーズです。残りのn-1枚の円盤をwork番目の杭からdest番目の杭に移動させます。（from番目の杭を経由します。）という命令を出しています。

fromは移動元の杭を、workは作業用の杭を、destは移動先の杭を便宜的に表しています。しかし、fromは0番目の杭で、workは1番目の杭で、destは2番目の杭で、2回目の手順は2番目に大きい円盤が0番目の杭から1番目の杭へ移ってるはずだから、それはどういうコードの流れでなっているのかな？と考えてはいけません！
最初の「再帰処理を理解するコツ」で述べましたが、制御変数の変化を考えて処理の流れを直接追うことが難しいので、途中経過はブラックボックスのままでよいのです。
それこそが再帰処理の本質なのです。

---

出力結果

出力結果は下記の通りとなります。

3
--
0: 3 2 1
1:
2:
--
0: 3 2
1:
2: 1
--
0: 3
1: 2
2: 1
--
0: 3
1: 2 1
2:
--
0:
1: 2 1
2: 3
--
0: 1
1: 2
2: 3
--
0: 1
1:
2: 3 2
--
0:
1:
2: 3 2 1

以上により、再帰処理を使って上でハノイの塔を解けたことが確認できました。