ハノイの塔を４回回したい

Question

ハノイの塔を４回回したいです。

# -*- coding: utf-8 -*-


def hanoi(n, x, y, z):
  count = 0
  while count < 4:
    count += 1
    if count == 1:
        print("{}→{}".format(x, y))
    else:
        hanoi(n-1, x, z, y)
        print("{}→{}".format(x, y))
        hanoi(n-1, z, y, x)
  return count

count = hanoi(3, "A", "C", "B")

とコードを書いて実行すると
RecursionError: maximum recursion depth exceeded while calling a Python object
と無限ループになってしまいました。
何が問題でどう直せば良いのでしょうか？

Comments

[Lhankor_Mhy]

『４回回したい』とは具体的にはどのようなことをしたいのでしょうか。ハノイの塔を4回解きたいということですか？

[退会済みユーザー]

円盤を４回動かしたいということです。この場合、７回動かして完成させるということですが、４回目で終了させたいということです。

Answer 1

とりあえず無限ループするのは、再帰の終了条件が存在しないため、nがマイナスになっても延々と再帰するコードになっているからです。
「どう直せばいいか」については↓この質問にヒントがあると思います。
Python - ハノイの塔の実装方法(83188)｜teratail

また、ステップのカウントですが、現状ですと再帰関数を呼び出すと0に戻ります。
これを解決するにはグローバル変数にするか、引数にする必要があるでしょう。

Comments

[退会済みユーザー]

ありがとうございます。
# -*- coding: utf-8 -*-

def hanoi(n, x, y, z,count):
while count > 4:
count += 1
if count == 1:
print("{}→{}".format(x, y))
else:
hanoi(n-1, x, z, y)
print("{}→{}".format(x, y))
hanoi(n-1, z, y, x)
return count

x = hanoi(3, "A", "C", "B",0)

[退会済みユーザー]

とコードを書いて実行したら、0 と出力されました。while文を通ったらすぐにreturn count　に行ってしまって...。何が間違っているのでしょうか？

[Lhankor_Mhy]

不等号が逆向きになっているからでは。

Answer 2

円盤の数がnでxが移動元でyが移動先とすれば

def hanoi(n, x, y, z):
  count = 0
  if n > 0:
    # n-1枚をxからzへ移動する
    count += hanoi(n-1, x, z, y)
    # xにはn枚目の円盤がありyにはnより大きな円盤はないはずなので
    print("move disk {} from {} to {}".format(n, x, y))
    count += 1
    # n-1枚をzからyへ移動する
    count += hanoi(n-1, z, y, x)
  return count

count = hanoi(4, "A", "B", "C")

上のコードでは円盤が4枚あるなら第一引数は4とする考え方です

「n-1枚分の移動を自分自身で解いた上で、n枚目の移動をし・・・」というふうに考えるのがハノイの塔を再帰呼び出しで解く場合の典型的な考え方と思います。そこには「関数の中で無条件に4回ループさせる」という論理は出てこないと思います。