ハノイの塔の実装方法

Question

ハノイの塔の実装方法がわからず困っています。
https://p--q.blogspot.jp/2014/06/python13.html
のリンクの通りコードを書くと

# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
    if n == 1:
        print("{}→{}".format(x, y))
    else:
        hanoi(n-1, x, z, y)
        print("{}→{}".format(x, y))
        hanoi(n-1, z, y, x)

print(hanoi(3, "A", "C", "B"))

で、このファイルを実装すると

 A→C
 A→B
 C→B
 A→C
 B→A
 B→C
 A→C

のように７回出力されます。
理解できないのが、なぜfor文やwhile文を使っていないのに
この場合、

else:
        hanoi(n-1, x, z, y)
        print("{}→{}".format(x, y))
        hanoi(n-1, z, y, x)

が何回も呼ばれるのかということです。
http://www13.plala.or.jp/kymats/study/C++/Hanoi/Hanoi.html
のURLを見ると
＃＃＃＃＃
n-1 枚の円盤を棒Aから棒Bへ移動する場合と
棒Bから棒Aへ移動する場合は交互に訪れる。
＃＃＃＃＃
という部分を実装しているとは思うのですが、
このリンクのサイトの図の
■3枚の円盤を移動する手順
のどの部分が＃＃＃＃＃で囲った説明を表現しているのかもわかりません。
なぜ hanoiメソッドで表現されるシンプルなコードでハノイの塔が実装できるのでしょうか？

Answer 1

hanoi(3, "A", "C", "B")
    // 3 != 1:  goto else
    hanoi(2, "A", "B", "C")
    |   // 2 != 1:  goto else
    |   hanoi(1, "A", "C", "B")
    |   |   // 1 == 1:  goto if
    |   |   print("A -> C")         // A -> C
    |   print("A -> B")             // A -> B
    |   hanoi(1, "C", "B", "A")
    |   |   // 1 == 1:  goto if
    |   |   print("C -> B")         // C -> B
    print("A -> C")                 // A -> C
    hanoi(2, "B", "C", "A")
    |   // 2 != 1:  goto else
    |   hanoi(1, "B", "A", "C")
    |   |   // 1 == 1:  goto if
    |   |   print("B -> A")         // B -> A
    |   print("B -> C")             // B -> C
    |   hanoi(1, "A", "C", "B")
    |   |   // 1 == 1:  goto if
    |   |   print("A -> C")         // A -> C

なぜ hanoiメソッドで表現されるシンプルなコードでハノイの塔が実装できるのでしょうか？

解法自体が単純なルールで表現できるからです．

1. スタートにあるn枚のうち，上からn-1枚を「なんとかして」一時領域に移す（n == 1の時は何もしない）
2. スタートに残ったものをゴールに移す
3. すでにゴールにある円盤は無視していい（この先ゴールにある円盤より大きい円盤を動かすことはない）ので，残った n-1 枚を移動する問題と考えて手続き 1 に戻る

コードと照らし合わせると，２つのprint文が手続き 2，else句の一度目の再帰が「なんとかして」部分，二度目の再帰が手続き 3 に相当するはずです．

Comments

[退会済みユーザー]

ありがとうございます。ハノイの塔の仕組みが理解できました！
何点か質問がありまして、
3.一時領域をスタート，スタートを一時領域として（役割を交換して），1に戻る
に関してですが、スタート，スタートを一時領域　とはどういう意味でしょうか？
また、1.スタートにあるn枚のうち，上からn-1枚を一時領域に移す　ですが
１のプロセスでn-1枚の全部を一時領域に移すのも何プロセスかありますよね？そのため、else:
の中で、hanoi(n-1, x, z, y)・hanoi(n-1, z, y, x)と呼び出しているということなのでしょうか？

[tamy]

> スタート，スタートを一時領域　とはどういう意味でしょうか？

基本的なハノイの塔って，場所（棒）が３つありますよね？
スタート：最初に n 枚が置いてある場所（質問文中では棒A）
ゴール：最終的に移動したい場所（質問文中では棒C）
一時領域：スタートでもゴールでもない場所（質問文中では棒B）

目的はスタートからゴールに全ての円盤を移すことですが，「小さい円盤の上には大きい円盤を置けない」という制約から，どうしても一時的に円盤を待避しておく場所（一時領域）が必要になります．

> １のプロセスでn-1枚の全部を一時領域に移すのも何プロセスかありますよね？そのため、else:
の中で、hanoi(n-1, x, z, y)・hanoi(n-1, z, y, x)と呼び出しているということなのでしょうか？

そうです．
ここの部分，少し記述を修正します．

Answer 2

hanoiは再帰関数だからです。

再帰処理とは
再帰関数を理解する方法を教えてください

Answer 3

再起呼び出しをしているからです。
実行をトレースしてみてください。

Comments

[退会済みユーザー]

再起呼び出しをしているのはわかります。
ただ、else:　文の中の
hanoi(n-1, x, z, y)　と　hanoi(n-1, z, y, x)　の引数が変わっているのが理解できなくて。最初のhanoiメソッドでは x, z, y　と引数を渡しているのに、２番目のhanoiメソッドでは z, y, x　と引数を渡していてなぜその順番が変わっているのでしょうか？

[jm1156]

ハノイの塔のアルゴリズムがわかっているならわかるはず。わからないなら調べましょう。