1

私は再帰がプロローグでどのように機能するかを理解していないと思います

次のコード（べき関数）

pow(_,0,1).
pow(X,Y,Z) :-
  Y1 is Y - 1  ,
  pow(X,Y1,Z1) ,
  Z is Z1*X
  .

次のトレースを作成します。

[trace]  ?- pow(2,2,X).
   Call: (6) pow(2, 2, _G368) ? creep
   Call: (7) _G444 is 2+ -1 ? creep
   Exit: (7) 1 is 2+ -1 ? creep
   Call: (7) pow(2, 1, _G443) ? creep
   Call: (8) _G447 is 1+ -1 ? creep
   Exit: (8) 0 is 1+ -1 ? creep
   Call: (8) pow(2, 0, _G446) ? creep
   Exit: (8) pow(2, 0, 1) ? creep
   Call: (8) _G450 is 1*2 ? creep
   Exit: (8) 2 is 1*2 ? creep
   Exit: (7) pow(2, 1, 2) ? creep
   Call: (7) _G368 is 2*2 ? creep
   Exit: (7) 4 is 2*2 ? creep
   Exit: (6) pow(2, 2, 4) ? creep

最後の状態：'Z is Z1*X'がどのように機能するのかわかりません。この関数はいつ呼び出されますか？ベースケースに達したとき？ベースケースはどのように呼び出されますか？

ありがとう

4

3 に答える 3

2

要点は、それは関数powではないということです。述語です。Prolog は を実際に評価するのではなく、その条件を満たそうとします。pow

そして、最初の条項に到達するのはいつですか？毎回試されています。ただし、2 番目の引数が 0 で、3 番目の引数が 1 でない限り (または、これらの値で統一できる変数でない限り)、失敗します。そして、最初の句が失敗すると、2 番目の句が試行されます。

于 2011-10-17T21:03:48.070 に答える
1

アスタリスク (*) が付いたトレース内のすべての行は、「Z is Z1 * X」ルールを使用しています。

このコードは、累乗関数の次の再帰的定義を提供することによって機能します。

  1. すべての X に対して X^0 = 1。
  2. X^Y = X^(Y-1) * X

Z、Z1、および Y1 変数は、Prolog が中間結果を参照する方法を必要とするという事実の成果物です。Y-1 Y1 と呼び、X^(Y-1) Z1 と呼びます。

これは、Y = 0 になるまで再帰の各レベルで指数 (Y) を 1 ずつ減らして (Y1 を生成)、ベース ケースに到達し、定義の最初のケースが適用されます。

于 2011-10-17T20:58:32.087 に答える