説明を簡略化するためにどの棒からどの棒に移動するか、棒の番号だけで示します。 0から2 0から1 2から1 0から2 1から0 1から2 0から2 ここで、最初の状態と手順3の後の状態に着目しましょう。最初の状態から手順3の後の状態にするには、上の2つをまとめて真ん中に移動させればよいはずです。円盤が2つの場合の移動の手順はすでに分かっているので、その手順に従って手順3の後の状態にすることができます。 そして手順4の後の状態と最後の状態に着目します。手順4の後の状態から最後の状態にするには、真ん中の2つの円盤をまとめて右の棒に移動させればよいはずです。これも同じ要領で2つの円盤を右に移動できます。 全部移動できたので、円盤3つをまとめて移動する手順が確立されました。 同じ要領で円盤が何個に増えても移動させることができます。つまり以下のような手順になります。円盤の数をnとします。 左の棒から
![再帰でハノイの塔を攻略せよ](https://cdn-ak-scissors.b.st-hatena.com/image/square/6e84fc6ab06f31b2e64248cbfc92fe06deb5bab5/height=288;version=1;width=512/https%3A%2F%2Fimage.itmedia.co.jp%2Fimages%2Flogo%2F1200x630_500x500_ait.gif)