関数型プログラミング事始め (27) 再帰プログラミング(3)
関数型プログラミングがはじめての方へ贈る入門の書
前節：再帰プログラミング(2) 次節：高階関数(1)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)
(4) 再帰プログラミング演習
ここでは再帰プログラミングの典型的な例を見ていくことにします。再帰プログラミングの例を見て、再帰プログラミングに慣れて、再帰プログラミングが自然にできるようになっていくでしょう。
OK! ISLispを使って関数型プログラミングの手習いをやっていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。
> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>
(a) クイックソート
最初の再帰プログラミングの例として、「クイックソート」を見ていきます。クイックソートは適当に基準値（ピボット）を選び、ピボットと比較して、小さいものと大きいものに二分します。これを二分したものが１個になるまで繰り返していくと、つまり「再帰で同じプログラムを呼び出す」と、ソートが完成するというものです。
このクイックソートは計算量がO(n log n)で済むという優秀なアルゴリズムです。あまりにも優秀なので多くのプログラミング言語ではライブラリとして言語仕様の一部となっています。つまり手作りする必要はありません。しかしその動作原理を学ぶことは重要です。それに再帰プログラミングの典型的な例となります。
ISLisp>
(defun qsort (list) (if (null list) list (qsort2 (car list) (cdr list) nil nil) ))
QSORT
ISLisp>
(defun qsort2 (p list left right)
(if (null list)
(append (qsort left) (cons p (qsort right)))
(if (< (car list) p)
(qsort2 p (cdr list) (cons (car list) left) right)
(qsort2 p (cdr list) left (cons (car list) right)) )))
QSORT2
ISLisp>(qsort '(2 1 3 5 4))
(1 2 3 4 5)
関数qsortは引数をピボット、ソート対象のリスト、左側（ピボットより小さい要素）のリスト、右側（ピボット以上の要素）のリストのようにするための調整的な関数です。Common Lispであれば、&optional 引数や&aux引数がありますので、この関数を用意する必要はありませんが、ISLispではありませんので、この関数を用意しています。
関数qsort2がクイックソートの本体です。ソート対象のリスト list の要素がなくなれば((null list)が真になれば)、左側のリストをソーティング(qsortを再帰で関数呼び出し）をして、ピボットと右側のリストを連結したリストをソーティングしたものを連結します。
listが空でなければ、listの先頭(car list)を取り出し、これとピボットと大小比較をします。先頭の要素がピボットよりも小さければ、左側のリストに連結し、そうでなければ右側のリストに連結します。これらを引数にしてqsort2の関数を再帰呼び出しをします。
これらの様子を(2 1 3 5 4)のリストを例にして、見ていくことにします。
(1)
list: 2 1 3 5 4
(2)
pivot: 2 ;適当に選んだピボット（今回はlistの先頭）
list: 1 3 5 4
left:
right:
(3)
pivot: 2
list: 3 5 4 ; listの先頭の2を取り出す
left: 1 ; ピボットの2より小さいので左側に連結
right:
(4)
pivot: 2
list: 5 4 ; listの先頭の3を取り出す
left: 1
right: 3 ; ピボットの2以上なので右側に連結
(5)
pivot: 2
list: 4 ; listの先頭の5を取り出す
left: 1
right: 5 3 ; ピボットの2以上なので右側に連結
(6)
pivot: 2
list: ; listの先頭の4を取り出す
left: 1
right: 4 5 3 ; ピボットの2以上なので右側に連結
(7)
pivot: 2
list: ; listが空なので以下を実行
・左側のリスト (1) をソートするために再帰呼び出し(qsort '(1))をした結果
・ピボット 2
・右側のリスト (4 5 3)をソートする(qsort '(4 5 3))の結果
上記の３個を連結したリストがソーティング結果になります。
クイックソートはまさに再帰プログラミングの典型的な例になります。詳細ははじめてのLisp関数型プログラミングのpp.160-162にありますので参照してください。
(b) ハノイの塔
ハノイの塔は3本の柱に大きさの異なる複数の円盤が刺さっているものです。規則としては、(1)円盤を柱から柱へ移動するときは柱に刺さっている一番上の円盤を１枚だけ取り出し別の柱に移動することができ、(2)円盤を重ねるときに、既に柱に刺さっている円盤の上には大きい円盤は重ねることができません。
例えば、以下のようにハノイの塔は円盤を移動します。1の柱の3枚の円盤を3の柱に移動します。
(1)
1: 1 2 3 ; 1の柱に上から大きさ1の円盤、2の円盤、3の円盤が刺さっている
2:
3:
(2)
1: 2 3 ; 一番上の大きさ1の円盤を取り出す
2:
3: 1 ; 1の柱から取り出した円盤を3の柱に移動
(3)
1: 3
2: 2 ; 1の柱から大きさ2の円盤を2の柱に移動
3: 1
(4)
1: 3
2: 1 2 ; 3の柱から大きさ1の円盤を移動
3:
(5)
1:
2: 1 2
3: 3 ; 1の柱から大きさ3の円盤を移動
(6)
1: 1 ; 2の柱から大きさ1の円盤を移動
2: 2
3: 3
(7)
1: 1
2:
3: 2 3 ; 2の柱から大きさ2の円盤を移動
(8)
1:
2:
3: 1 2 3 ; 1の柱から大きさ1の円盤を移動
それではこのハノイの塔の再帰プログラミングを見ていきましょう。fromの柱から、toの柱に移動するハノイの塔のプログラムで、円盤の移動を(移動元 . 移動先)のドット対(ペアの要素を格納するデータ型でリストの特殊な形式で実装)で表現しています。
ISLisp>(defun hanoi (n) (hanoi2 n 'from 'to 'other))
HANOI
ISLisp>
(defun hanoi2 (n from to other)
(if (= n 1)
(cons (cons from to) nil)
(append
(hanoi2 (- n 1) from other to)
(hanoi2 1 from to other)
(hanoi2 (- n 1) other to from) )))
HANOI2
ISLisp>(hanoi 3)
((FROM . TO) (FROM . OTHER) (TO . OTHER) (FROM . TO) (OTHER . FROM) (OTHER . TO) (FROM . TO))
関数hanoiは&optional引数や&aux引数がISLispにないために、用意した調整用の関数です。関数hanoi2が本体になります。
hanoi2で円盤の枚数nが1枚であったときは、fromの柱からtoの柱へ移動して終わりなので、from と toのドット対(cons from to)を要素とするリスト(cons (cons from to))を返します。
円盤が2枚以上のときは、(a) fromからotherの柱へ(n - 1)枚の円盤を移動し、次に(b) fromからtoの柱へ1枚の円盤を移動し、最後に(c) otherからtoへ(n-1)枚の円盤を移動した結果の移動リストを連結します。
このとき、(a)、(c)が(n - 1)の再帰呼び出しになっています。(b)は再帰呼び出しする必要はなく、直接の移動である(from to)を返すだけになります（これおを末尾呼び出しと言います）が、ここでは統一も考えて、再帰呼び出しにしています。
ハノイの塔がおもしろいと思われた方は、4本ハノイの塔も考えてみてください。3本ハノイと比較して、移動回数が極端に減り、世界が滅亡します（ハノイの塔で64枚の円盤を移動すると世界は滅亡するという伝説になっています。でも安心してください。64枚の移動には多くの時間が必要です。
ということでここでの結論「再帰で世界は平和」です。
(予告) 3.2 高階関数
次回はいかにも関数型プログラミング！という高階関数を見ていくことにします。お楽しみに！
よろしければサポートをお願いします！