再帰関数における引数の入れ替え （ハノイの塔を例に）

再帰の代表例と言えば、フィボナッチ数列、階乗計算……など色々ありますが、中でも有名にしてちょっと難しい例に、そう、「ハノイの塔」があります。一説によるとドルアーガの塔クリアより難解、何度もZAPされて理解を諦めた強者たち数知れず、らしいです。噂ですけど。
その説明は「ハノイの塔　考え方」などの検索ワードでググればたくさん出てきますので各自調べるといいと思う……で済ませると「ggrks」の5文字ですべてを終わらせる現代の悲しい風潮に棹差すかと思いますので、簡単に説明します。まず、以下の図をご覧ください。

図１

最初この状態から始まって

図２

取り敢えず5の円番をC軸に移して

図３

そして4番の円盤も移して……と続けて行って最終的にすべての円盤をc軸に移し替えるわけです。
注目してもらいたいのは、図２のb軸に4枚の、図３のa軸に3枚のハノイの塔が出来ていることです。
つまり、n枚の円盤のハノイの塔を解くためn番目（一番大きな円盤）をc軸へ移し替えるには、a軸もしくはb軸にn-1枚のハノイの塔が出来るわけです。（１.一度に一枚の円盤しか動かせない 2.より大きな円盤はより小さな円盤の上には置くことが出来ない、というルール上、必ずそうなります）
言い換えますと、n枚のハノイの塔を解くには(n-1)枚のハノイの塔を解けばよく、そのためには((n-1)-1)枚のハノイの塔を解けばよく、そのためには(((n-1)-1)-1)枚のハノイの塔を解けばよく……はい、再帰です。
しかし、出発する軸（(n-1)枚のハノイの塔ができている軸）が、aになったりbになったり変わっていますね。それを、再帰関数の引数の順序を入れ替えることで実現します。

これをSchemeで書くとこうなります。

1:(define (move-disk disk from to)
2:  (display "Move disk ")
3:  (display disk)
4:  (display " from ")
5:  (display from)
6:  (display " to ")
7:  (display to)
8:  (display " . ")
9:  (newline))
10:
11:(define (hanoi n)
12:  (hanoi-aux n 'a 'c 'b))
13:
14:(define (hanoi-aux n from to free)
15:  (if (= n 1)
16:      (move-disk 1 from to)
17:      (begin
18: (hanoi-aux (- n 1) from free to)
19: (move-disk n from to)
20: (hanoi-aux (- n 1) free to from))))

湯浅太一 著『Scheme入門』　岩波書店　１９９１年

より（ただし行番号は引用者が付けた）
18行目で
(n-1)枚めの円盤の目的地を to から free へ入れ替え、
19行目で
(n-1)枚めの円盤を from から to へ移し
20行目で
(n-1)枚めの円盤の出発地（軸）を free にして目的軸を to に戻しているわけですな。実際に
(hanoi 4)
を、Gaucheで実行すると以下のように出力されます。

gosh> Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .
Move disk 3 from a to b .
Move disk 1 from c to a .
Move disk 2 from c to b .
Move disk 1 from a to b .
Move disk 4 from a to c .
Move disk 1 from b to c .
Move disk 2 from b to a .
Move disk 1 from c to a .
Move disk 3 from b to c .
Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .
#<undef>

はい、解けました。が、hanoi_auxに渡される引数は (4, a, c, b)のはずなのに
from c to a
やら
from b to c
やら出てくるの？　と頭がこんがらかるので、途中の(hanoi_aux)関数の引数を表示させるために(display)関数を元のコードに突っ込みます。

(define (move-disk disk from to)
  (display "Move disk ")
  (display disk)
  (display " from ")
  (display from)
  (display " to ")
  (display to)
  (display " . ")
  (newline))

(define (hanoi n)
  (hanoi-aux n 'a 'c 'b))

(define (hanoi-aux n from to free)
  (if (= n 1)
      (move-disk 1 from to)
      (begin
;ここから
    (display " from=")
    (display from)
    (display " to=")
    (display to)
    (display " free=")
    (display free)
    (newline)
;ここまで新たに挿入
    (hanoi-aux (- n 1) from free to)
    (move-disk n from to)
    (hanoi-aux (- n 1) free to from))))

すると出力は

gosh> from=a to=c free=b
from=a to=b free=c
from=a to=c free=b
Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .
Move disk 3 from a to b .
from=c to=b free=a
Move disk 1 from c to a .
Move disk 2 from c to b .
Move disk 1 from a to b .
Move disk 4 from a to c .
from=b to=c free=a
from=b to=a free=c
Move disk 1 from b to c .
Move disk 2 from b to a .
Move disk 1 from c to a .
Move disk 3 from b to c .
from=a to=c free=b
Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .
#<undef>

困ったことにさらにわけが分からなくなりました。ので、C言語マイスターヤブサメ先生を頼りましたところ、「コード見せて」とのこと。なのでgithubに上記のコードをあげると……

---

ヤブサメ先生（通称「センセ」）とは？
日本人なのに「Nina_Petipa」と名乗る男性。サイト０から作るソフトウェア開発の管理人として有名。若きC言語マニア。C言語を愛するあまり、何から何までC言語（もしくはアセンブリ言語）で実装を試みる。上記サイトの内容をamazonでKindle版として販売中（作者名は「yabusame2001」）なので、Kindleをお持ちの方はお布施と思って購入してあげてください。
githubアカウントはgithub.com/Ninals-GitHub
最近の口癖は「40秒でやれ」「草生える」「持ち株が下がった」

---

40秒でCで書き換えてくれやがりました。サイヤ人か。

1:#include <stdio.h>
2:#include <stdlib.h>
3:
4:static void move_disk(int disk, char from, char to);
5:static void hanoi_aux(int n, char from, char to, char free);
6:
7:static void move_disk(int disk, char from, char to)
8:{
9:  printf("Move disk %d from %c to %c . \n", disk, from, to);
10:}
11:
12:static void hanoi_aux(int n, char from, char to, char free)
13:{
14: if (n == 1) {
15:     move_disk(1, from, to);
16:     return;
17: }
18:
19: hanoi_aux(n - 1, from, free, to);
20: move_disk(n, from, to);
21: hanoi_aux(n - 1, free, to, from);
22:}
23:
24:int main(int argc, char *argv[])
25:{
26: int stage;
27:
28: if (argc != 2) {
29:     printf("usage:./%s stage\n", argv[0]);
30:     return(-1);
31: }
32:
33: stage = atoi((const char*)argv[1]);
34:
35: if (stage <= 0) {
36:     printf("stage option must be a positive integer\n");
37:     return(-1);
38: }
39:
40: hanoi_aux(stage, 'a', 'c', 'b');
41:}

Nina_Petipa作　(ただし行番号は引用者が付けた）

「センセ、Lisp読めるんだ？」と聞いたところ
「Lisp読めない。でも雰囲気でやりたいこと分かった。」とのこと。雰囲気でCに完全翻訳するとか、サイヤ人か。
ともかく
gcc -o hanoi ./hanoi.c
でコンパイルしまして
~$ ./hanoi 4
を実行。

Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .
Move disk 3 from a to b .
Move disk 1 from c to a .
Move disk 2 from c to b .
Move disk 1 from a to b .
Move disk 4 from a to c .
Move disk 1 from b to c .
Move disk 2 from b to a .
Move disk 1 from c to a .
Move disk 3 from b to c .
Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .

うん、できた。が、やっぱり引数がどうなってんのか分かんないや、ということで引数を出力させるコードを一行、突っ込みます。

#include <stdio.h>
#include <stdlib.h>

static void move_disk(int disk, char from, char to);
static void hanoi_aux(int n, char from, char to, char free);

static void move_disk(int disk, char from, char to)
{
    printf("Move disk %d from %c to %c . \n", disk, from, to);
}

static void hanoi_aux(int n, char from, char to, char free)
{
    if (n == 1) {
        move_disk(1, from, to);
        return;
    }

    /*ここから付け足し*/
    printf("from= %c to= %c free= %c \n", from, to, free);
    /*ここまで*/

    hanoi_aux(n - 1, from, free, to);
    move_disk(n, from, to);
    hanoi_aux(n - 1, free, to, from);
}

int main(int argc, char *argv[])
{
    int stage;

    if (argc != 2) {
        printf("usage:./%s stage\n", argv[0]);
        return(-1);
    }

    stage = atoi((const char*)argv[1]);

    if (stage <= 0) {
        printf("stage option must be a positive integer\n");
        return(-1);
    }


    hanoi_aux(stage, 'a', 'c', 'b');
}

これをコンパイルし直して実行しますと

~$ ./hanoi 4
from= a to= c free= b
from= a to= b free= c
from= a to= c free= b
Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .
Move disk 3 from a to b .
from= c to= b free= a
Move disk 1 from c to a .
Move disk 2 from c to b .
Move disk 1 from a to b .
Move disk 4 from a to c .
from= b to= c free= a
from= b to= a free= c
Move disk 1 from b to c .
Move disk 2 from b to a .
Move disk 1 from c to a .
Move disk 3 from b to c .
from= a to= c free= b
Move disk 1 from a to b .
Move disk 2 from a to c .
Move disk 1 from b to c .

うん、やっぱり分からん。のでセンセに聞いたところ「スタックだよ」との答えが。あの、すんません、戦闘力6〜8桁のサイヤ人の言葉じゃなくて、戦闘力一桁の地球人にも分かる言葉でお願いします。
しょうがなくセンセがくれたのが下の図

（「猿も木から」と言うように、センセも珍しく「3番move_disk(1, b, c)」を「3番move_disk(1, c, a)」と書き間違っています）

hanoi(＊, ＊, ＊)の左に打ってあるのは、センセのCコードの行数ね。

「右側は自分で埋めろ。40秒でな！」とのこと。40秒は無理だろ。必死になってこの図を理解しつつ、何とか深夜過ぎて未明に右側を書き上げました。

つまり、どうやらhanoi関数がhanoi_aux関数を呼び出す都度、
・まず19行目のhanoi_auxに引数を渡し｛ただし(n, from, to, free)から（n-1, from, free, to）に入れ替わっている｝、
・move_disk関数にそれと同じ引数を渡し｛ただし(n, from, to, free)から（n, from, to）に入れ替わっている｝、
・21行目のhanoi_aux関数にもそれと同じ引数｛ただし(n, from, to, free)から（n-1, free, to, from）に入れ替わっている｝を渡していて、
それが再帰で繰り代えされているわけですね。

こうやって引数の位置を変えることで、円盤が元ある軸、円盤を移す先の軸、を上手く入れ替えているわけですな。あー長かったけれどこれでおしまいっと。
（＊図が下手なのは勘弁してください）