ハノイの塔を用いて再帰的アルゴリズムを考えてみる。

#前提
プログラミング始めて1ヶ月のクソザコ大学生によるpythonコードの為いろいろつっこみ所がある可能性、またかなり基本的な事をあたかも難しいことのように表記している可能性が考えられるが、自己満なのでいいのである。

#経緯
Atcoderのある問題の解答の一つに

def func(x):
    ...
    ...
    return null + func(y)

のように、関数を定義するコード内にその関数が出現するという空前絶後前代未聞の表記が現れた。

初学者の僕は、「いやいやいや、卵が先か鶏が先かかなんかのギャグか？」と思ったが、どうやらこれは再帰関数というものらしい。
ぱっと見感覚的に理解できそうだが、せっかくなのでどうやら再帰的アルゴリズムを扱うときによく出てくるらしいハノイの塔を用いて軽く考察してみる。

#ルール
おなじみハノイの塔。
・A,B,Cの順に並んだ3本の柱の柱Aに最初N段の円盤が小さいものが上になるように置かれている。
・円盤は1枚ずつ移動できる。
・自分より小さな円盤の上にその円盤を置くことはできない。
・0 < N
・Nは整数。

###入力
円盤の枚数Nを出力する。

input

N

###出力
操作毎の動き出力する

例

output

AからB
AからC
BからC

#考察

ともかくコードを書いてみたが再帰関数の使い方がわからないので、ネットで拾ったコードを参考に書いてみた。

hanoi.py

n = int(input())

def change(n, a, b, c):
    if n == 1:
        print(a, "から", c)
    else:
        change(n-1, a, c, b)
        print(a, "から", c)
        change(n-1, b, a, c)

change(n, "A", "B", "C")

###結果

3
A から C
A から B
C から B
A から C
B から A
B から C
A から C

まあ他人のを真似て書いたので動いて当たり前なのである。

まず柱Aの一番下の円盤を柱Cに移す為に、柱Aの上からn-1個の円盤を柱Bに移す。
その作業にchange(n-1, a, c, b)が使え、次に柱Aにある1つの円盤を柱Cに移す。
この時、柱Bにn-1個の円盤が積み重ねてある状態のためこれまたchange(n-1, b, a, c)で完了する。

といった手順は分かる。

しかしコードの意味が分からない。
こんなに簡単でいいのか。


再帰関数の例としておそらく最も簡単な1からnまでの和を求める関数

sum.py

def sum(n):
    if n == 0:
        return n
    else:
        return n + sum(n-1)

この例は、なんかnが0になるまでループしてるんだな～（小並）って感じで分かる。
戻り値が整数値を取るために理解しやすい。

本題のコードだが、途中で「えっ、この関数なにを返すんだっけ？」となりがちである（僕はなった）。

とりあえずデバッガーで動きを見ようとしたが、関数だからか僕の知識不足か知らないが細かい動きが見れなかった。


なのでcountとcounterという変数を用意してあげて出力ごとにコードのどの部分でprint()が実行されているのか見ることにした。

そのコードがこちら

hanoi_2.py

n = int(input())
count = 0
counter = 0

def change(n, a, b, c):
    global count
    global counter
    if n == 1:
        count += 1
        print(a, "から", c,count,counter)
    else:
        change(n-1, a, c, b)
        counter += 1
        print(a, "から", c,count,counter)
        change(n-1, b, a, c)

change(n, "A", "B", "C")
print(count)
print(counter)

###結果

A から C 1 0
A から B 1 1
C から B 2 1
A から C 2 2
B から A 3 2
B から C 3 3
A から C 4 3
4
3

なんとなく理解した。

n = 1になるまでif文をジグザグして、n = 1になったら下まで処理して次いく
これを繰り返す

って感じだ。（幼並）

例えばn = 3の場合、change()とprint()を略して順に書くと

(3, A, B, C)

  (2, A, C, B)
    (1, A, B, C) "AからC"
         "AからB"
    (1, C, A, B) "CからB"

  "AからC"

  (2, B, A, C)
    (1, B, C, A) "BからA"
         "BからC"
    (1, A, B, C) "AからC"

となるわけだ。
本質はfor文と変わらないのか、、？




「まず柱Aの一番下の円盤を柱Cに移す為に、柱Aの上からn-1個の円盤を柱Bに移す。
その作業にchange(n-1, a, c, b)が使え、次に柱Aにある1つの円盤を柱Cに移す。
この時、柱Bにn-1個の円盤が積み重ねてある状態のためこれまたchange(n-1, b, a, c)で完了する。」

これをそっくりそのままコーディングすると簡単に所望のプログラムが得られるが、それを1つ1つ追ってみるとかなりややこしい
という見た目と本質のギャップに頭が追いつかないが、眠いので考えるのは今度にしよう。

もう朝の5時だ。徹夜してしまった。

#結論
で、結局なにがしたかったんだ？

#参考
https://atcoder.jp/
https://ja.wikipedia.org/wiki/ハノイの塔
https://p--q.blogspot.com/2014/06/python13.html
http://www.howisit.jp/2018/05/01/recursive/