論理型言語(Prolog)入門～再帰編～

導入

最近、論理プログラミングの勉強を始めました。理解をより深めるために、自分の言葉でまとめたメモを投稿していこうと思います。今回は再帰編です。初めて学ぶ方は、ぜひ前回の「論理型言語(Prolog)入門」もご覧ください。

---

1. 再帰とは

再帰とは、繰り返し処理のことです。論理型言語では制御構造がないため、ループ構造が存在しません。そのため、再帰を用いてループ構造を実現します。

2. 再帰の基本構造

再帰は以下のような流れで作成を行う。

1. 単純解
   自明な解を設定する
2. 簡単化
   複雑度xの問題を複雑度x-1の問題にする
3. 再帰
   複雑度x-1の問題に同じ処理を適用する
4. 合成
   複雑度xの問題の解を複雑度x-1までの解と合わせる

3. 再帰プログラムの例

階乗のプログラム

factorial.pl

factorial(0,1).
factorial(N,A) :-
    N >= 1,
    N1 is N - 1,
    factorial(N1,A1),
    A is N * A1.

factorial.plは階乗のプログラムであり、2つの引数を用意した。
1個目の引数が求めたい階乗の数であり、2個目がその解である。
再帰の基本構造とは以下のように対応している。

1. 単純解
   0の階乗を1とした
2. 簡単化
   数NをN1(N-1)に分解した
   この時、Nは1以上であるとした
3. 再帰
   N1に対して同じ処理を行い、その解をA1とした
4. 合成
   解AはN×A1で表されるとした

フィボナッチ数列のプログラム

fibonacci.pl

fibonacci(1,1).
fibonacci(2,1).
fibonacci(N,A) :-
    N >= 3,
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1,A1),
    fibonacci(N2,A2),
    A is  A1 + A2.

fibonacci.plはフィボナッチ数列のプログラムであり、2つの引数を用意した。
1個目の引数がN番目の項を指定する数であり、2個目がその値である。
再帰の基本構造とは以下のように対応している。

1. 単純解
   1番目の値を1とした
   2番目の値を1とした
2. 簡単化
   数NをN1(N-1)に分解した
   数NをN2(N-2)に分解した
   この時、Nは3以上であるとした
3. 再帰
   N1に対して同じ処理を行い、その解をA1とした
   N2に対して同じ処理を行い、その解をA2とした
4. 合成
   解AはA1+A2で表されるとした

4. 再帰の注意点

• 節は上から順に処理されるため、節の順番によって動作が大きく変わる
• 単純解の未設定や簡単化を行わないと、意図しない無限ループが発生する
• 変数を具体化（束縛）しないと文字列として評価され、正しく数値計算できない

まとめ

• 再帰を用いることでPrologでも繰り返し処理を行える
• 再帰には基本構造が存在する
• 再帰を用いる際にはいくつかの注意点が存在する

参考

以下のサイト・参考書が分かりやすく、参考にさせていただきました。
『Prologへの入門』(I.Bratko 著)
https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0