目次
再帰処理を使ってハノイの塔の解を求める
Pythonで再起処理をやってみます。
Python文法ってサブタイトルつけてますが・・文法的に再帰構文があるわけではなくて「再帰的な処理」のパターンも広義的に考えれば含むかな・・という程度のことです。
再帰処理とは
再帰（再帰的）は「（数学的には）定義の中に定義されるものが含まれていること」で、Pythonプログラムに置き換えてみれば「関数（自分）の中で自分を呼び出し、結果を受け取る」ような感じです。
用語的には。
- 自分自身を呼び出す処理を再帰的 (recursive)
- 再帰的な関数のことを再帰関数 (recursive function)
- 再帰的に関数を呼び出すことを再帰呼び出し (recursive call)
という呼び方をします。
再起処理は言葉だけだと、とてもイメージしづらいので、サンプル的に「ハノイの塔」の解を求めるプログラムをPythonで書きながら整理します。
ハノイの塔とは
有名なパズルで、下の図のように、3本の柱があって、一番左端（A)に何枚か（例では3枚）の円盤がささっているところからスタートします。
円盤を1枚ずつ動かして、真ん中の柱（B）に移すパズルです。
円盤は図のように全部大きさが違い、下の段ほど大きい円盤になっているのですが、動かす途中であっても、小さい円盤の上に、大きい円盤をのせてはいけません。
このルールを守って一枚ずつ動か菓子、以下のようになればOKです。
円盤の数が３枚なら「３ハノイ」、４枚なら「４ハノイ」のように、円盤の数＋ハノイで呼ぶのが一般的で、当たり前ですが、円盤の数が少ないほど簡単です。
ハノイの塔を解くアルゴリズム
このサイトによると、「２のN乗 －１（Nは円盤の数）」回で解けるのが最短手順とのことです。
つまり、円盤３枚なら手順は７回（２の3乗－1）で解けるということです。
ハノイの塔には、問題を解くアルゴリズムが存在し、上記のサイトの記事よれば。
となっています。
A(n)に対して内部でA(n-1)を用いるということは、A()という関数を再帰的に呼び出しているということなので、まさに「再帰処理」です。
pythonでの実装
早速、pythonでやってみました。
ほぼ、上記のアルゴリズムをソースにおとしただけです。
def hanoi(n, a, b, c):
hanoi_imp(n, a, b, c)
def hanoi_imp(n, a, b, c):
if n <= 0:
pass
else:
hanoi_imp(n - 1, a, c, b)
print(a + u" → " + b)
hanoi_imp(n - 1, c, b, a)
hanoi(3, "A", "B", "C")
引数のnに円盤の枚数をわたし、a,b,c には、表示用にA,B,Cの文字を渡します。
再帰呼び出しをするところで、引数で渡されてa,b,cの位置を入れ替えないといけない所が、ちょっと工夫が必要でしたが、ほぼ、まんまです。
この中で「pass」と書いているところが「何もしない」処理です。
あと、hanoi_imp()の中で、自分自身（hanoi_imp）を呼び出してます。
これが再帰処理です。
このテクニックを使うと「複雑に行われる処理を簡単に書くことができる」メリットがあるのですけど、慣れないと、結果がまったくイメージできない・・という悩ましいところがあります。
プログラムの実行結果
これを、math_hanoi.py という名前で保存して実行してみます。
python math_hanoi.py
結果は。
A→B
A→C
B→C
A→B
C→A
C→B
A→B
とりあえず、5ハノイまではプログラムの出力を見ながら、実際にやって回答を検証しましたが、OKでした。
6ハノイ以上は試してませんが、大丈夫と思います。
ではでは。
