Prologプログラミング: 再帰的プログラミング


再帰的プログラミング (recursive programming) は, Lisp, ML などの関数型言語や Prolog などの論理型言語で 非常に良く使われるプログラミング方法です. 再帰的な考え方に慣れると, for や while といった繰り返し構造よりも ずっとエレガントにプログラミングできます.

再帰的プログラミングが威力を発揮するのは, 数値処理よりも記号処理やリスト処理といった分野です. しかしここでは,再帰的プログラミングに慣れることを目的に, 数値処理を中心に説明します. SICStus Prologで利用できる算術計算については こちらを参照してください.

階乗

たとえば,階乗 n! は次のように再帰的に定義できます.

    n! = 1            (n=0のとき)
       = n * (n-1)!   (n>0のとき)
これを Prolog でプログラムすると以下のようになります. fact(N, F) は N! = F であることを表します.

    fact(0, 1).
    fact(N, F) :-
        N > 0,                    /* N > 0 をチェック */
        N1 is N-1,                /* N-1 を N1 に求める */
        fact(N1, F1),             /* N1! を F1 に求める */
        F is N*F1.                /* F は N*F1 とする */
一行目の事実は,0 の階乗が 1 であることを表します. 二行目の規則は, N が正のとき, N の階乗は N と N-1 の階乗の積であることを表します. N-1 の階乗を求めるのに,自分自身を再帰的に呼び出している点に 注意してください. ゴール ?- fact(100, F). で 100! を求めることができます. SICStus Prologでは任意長の整数を取り扱えるので, 100 の階乗でも正しく求められます.

もちろん,階乗は C でも簡単に再帰的に定義できます. この場合は,むしろ C のほうがわかりやすいかも知れません (任意長の整数を取り扱うことは簡単にはできませんが).


    int fact(n)
        int n;
    {
        if (n == 0)
            return 1;
        else
            return n*fact(n-1);
    }

再帰的なプログラムの動作は,最初はなかなかわかりにくいものです. 次のようにすると, Prolog のデバッガを使って, fact を呼び出す時の状況と実行結果を表示できます. 動作の理解のために利用してみて下さい.


    | ?- spy fact.                    /* factをスパイする */
    {debug}                           /* 自動的にデバッガに入る */
    | ?- fact(10,F).                  /* デバッガ中でfactを実行 */
     + 1  1  Call: fact(10,_64) ? l   /* l (エル) を入力 */
     + 4  2  Call: fact(9,_228) ? l
     省略
     + 31  11  Call: fact(0,_2082) ? l
     + 31  11  Exit: fact(0,1) ? l
     + 28  10  Exit: fact(1,1) ? l
     省略
     + 1  1  Exit: fact(10,3628800) ? l
    
    F = 3628800 ? 
    {debug}
    | ?- nospyall.                    /* スパイをやめる */
    {debug}
    | ?- nodebug.                     /* デバッガを終了 */
下線から始まる数 (_64など) は変数を表します. 数は Prolog 内部で付けられた変数番号を表しますので, 上と同じ番号になるとは限りません.

トレースの途中でデバッガから抜けるには l (エル)のかわりに a を入力します.

フィボナッチ数列

フィボナッチ数列は以下のように再帰的に定義されます.

    fib(n) = 0                    (n=0のとき)
           = 1                    (n=1のとき)
           = fib(n-1) + fib(n-2)  (n>1のとき)
これを Prolog でプログラムすると以下のようになります.

    fib(0, 0).
    fib(1, 1).
    fib(N, F) :-
        N > 1,                   /* N > 1 をチェック */
        N1 is N-1, fib(N1, F1),  /* N-1 に対する結果を F1 に求める */
        N2 is N-2, fib(N2, F2),  /* N-2 に対する結果を F2 に求める */
        F is F1+F2.              /* F を F1+F2 とする */
ゴール ?- fib(10,F). で 10 番目のフィボナッチ数列の値を求めることができます.

Collatzの問題,角谷(かくたに)の問題

ある自然数 n から始めて,次の操作を繰り返すとします.
  1. n が偶数なら2で割る (n = n/2)
  2. n が奇数なら3倍して1を足す (n = 3*n+1)
証明はまだされていませんが(つまり未解決の問題), どんな数から始めても必ず 1 になることが経験的に知られています.

たとえば,7 から始めると, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 と 16 ステップで 1 になります.

実際に, 1 になるかどうかを確かめる Prolog のプログラムを書いてみましょう.


    collatz(1).                   /* 1 になれば OK */
    collatz(N) :-
        N > 1, N mod 2 =:= 0,     /* 1 より大きい偶数かチェック */
        N1 is N//2, collatz(N1).  /* 2 で割った値について繰り返す */
    collatz(N) :-
        N > 1, N mod 2 =:= 1,     /* 1 より大きい奇数かチェック */
        N1 is 3*N+1, collatz(N1). /* 3倍して1足した値について繰り返す */
組込述語 =:= は,両辺の数式の値が等しいかどうかチェックする述語です. したがって N mod 2 =:= 0 は, N を 2 で割った余りが 0 かどうか, すなわち N が偶数かどうかをチェックしています. 数式中の N//2 は, N を 2 で割った商の整数部分を求めています.

上のプログラムだと途中経過がわからないので,次のように書換えます. write(N1), write(' ') で途中の値とスペースを 1 つ表示します.


    collatz(1).
    collatz(N) :-
        N > 1, N mod 2 =:= 0,
        N1 is N//2,
        write(N1), write(' '),
        collatz(N1).
    collatz(N) :-
        N > 1, N mod 2 =:= 1,
        N1 is 3*N+1,
        write(N1), write(' '),
        collatz(N1).
たとえば ?- collatz(27). を実行してみてください.

抽象的に定義された集合

ある集合 S は,次のような規則で定義されるとします.
  1. S は 0 を要素として含んでいる
  2. S が n を要素として含んでいるなら,2n+1 も要素として含まれている
  3. S が n を要素として含んでいるなら,3n+1 も要素として含まれている
  4. 上記以外に S の要素はない
たとえば,13 は S の要素でしょうか? 規則2と規則3をながめると,6 あるいは 4 が S の要素であれば, 13 も S の要素であることがわかります (さらに規則4により,それ以外の場合はありえないことがわかります). では,6 は S の要素でしょうか? 6 は 2n+1 の形でも 3n+1 の形でもないので,S の要素ではありません. では,4 は S の要素でしょうか? 規則3 より,1 が S の要素ならOKです. 同様に,0 が S の要素なら 1 は S の要素です. 規則1 より,0 は S の要素なので,結局 13 が S に含まれることがわかります.

これを, Prolog のプログラムで書いてみましょう. このプログラムは再帰的定義とバックトラックをうまく利用しています.


    inS(0).
    inS(N) :-
        N > 0, (N-1) mod 2 =:= 0,
        N1 is (N-1)//2, inS(N1).
    inS(N) :-
        N > 0, (N-1) mod 3 =:= 0,
        N1 is (N-1)//3, inS(N1).
二つ目の規則で,2n+1 の形の数について,n が S に含まれるかどうかを 調べています. 三つ目の規則は,3n+1 の形の数についてです. 2n+1 の形でもあり 3n+1 の形でもある数(たとえば13)については, 二つ目の規則を実行して失敗すれば, バックトラックして三つ目の規則が実行されることに注意してください.

ハノイの塔

ハノイの塔は,古代インドより知られている問題です.

半径が 1 から 3 までの 3 枚の円盤があるとします (以下,円盤1, 円盤2, 円盤3 と呼びます). 円盤の中心には穴が空いていて,棒に突きさすことができます. また,地面には 3本の棒 (以下,棒x, 棒y, 棒z と呼びます) が立っているとします.

最初は, 棒x に,上から順に,円盤1, 円盤2, 円盤3 がささっている状態から始めます. 「すべての円盤を 棒y に移せ」というのが問題です. ただし,円盤を移すときには以下の条件をまもらなければなりません.

  1. 移動できる円盤は,各棒の 1番上にあるものだけである
  2. 自分よりも小さな円盤の上には移動できない
Emacs 中 (あるいは Mule 中)で,M-x hanoi とすると,答を見ることができます. ぜひやってみてください.

円盤が 3枚ではなく, N 枚であってもすべての円盤を移動することが可能です (2^N に比例する時間が必要です) Emacs 中で,C-u N M-x hanoi としてみてください (Nの値は,せいぜい 7くらいまでにしましょう).

この問題は,再帰的に考えて解くことができます. 次のようにすれば, N枚の円盤を 棒X から 棒Y に移動することができます.

  1. N-1枚の円盤を 棒X から 棒Z に移動させる
  2. 円盤N を 棒X から 棒Y に移動させる
  3. N-1枚の円盤を 棒Z から 棒Y に移動させる
これを, Prolog のプログラムで書くと次のようになります (Emacs でのように実際に移動させるのではなく, どの円盤をどの棒からどの棒に移動させるのかを表示するだけです). ゴール ?- hanoi(3,x,y,z). で実行してみて下さい.

    hanoi(0, _, _, _).
    hanoi(N, X, Y, Z) :-
        N > 0, N1 is N-1,
        hanoi(N1, X, Z, Y),   /* N-1枚の円盤を 棒X から 棒Z に移動 */
        write('move '), write(N),
        write(' from '), write(X),
        write(' to '), write(Y), nl,
        hanoi(N1, Z, Y, X).   /* N-1枚の円盤を 棒Z から 棒Y に移動 */
一行目にある下線 _ は,匿名変数と呼ばれる変数で, その変数が一か所にしか現れない場合に用います. もちろん hanoi(0, _, _, _) ではなく hanoi(0, X, Y, Z) としても正しいプログラムです. 組込述語 nl は改行を行います.

練習問題

問題1
1! + 2! + … + N! を求める述語 factsum を定義しなさい.
問題2
正整数 A と B の最大公約数Gを求める述語 gcd(A,B,G) を定義しなさい. A と B の最大公約数は,ユークリッドの互除法により, 次のように再帰的に定義できます.

     gcd(A, B) = B                (A=0のとき)
               = gcd(B mod A, A)  (A>0のとき)
     
B を A で割った余り R は R is B mod A で求められます.

最初に戻る 前へ 次へ