1

我不认为我了解递归在 prolog 中的工作原理

以下代码（幂函数）

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，它试图满足它的条件。

什么时候到达第一个子句？每次都尝试过。但除非第二个参数为 0，第三个参数为 1（或者它们是可以与这些值统一的变量），否则它会失败。当第一个子句失败时，将尝试第二个子句。

于 2011-10-17T21:03:48.070 回答
1

跟踪中带有星号 (*) 的每一行都使用“Z 是 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) 减一（产生 Y1）直到 Y = 0 并且适用定义的第一种情况来达到基本情况。

于 2011-10-17T20:58:32.087 回答
1

您可以将其pow视为一个分为处理不同参数值的两个子句的函数。该函数是递归的，由第二个子句中的递归调用触发。但是在这个电话之后，还有事情要做，Z is Z1*1目标。这些“悬空”计算是在递归终止并再次控制向上的“气泡”时完成的，可以说是在返回的路上。（这种递归有一个名字，我不记得了）。

看看这个注释跟踪：

[trace]  ?- pow(2,2,X).
      % initial call
   Call: (6) pow(2, 2, _G368) ? creep
      % the second clause is picked for this call, 
      % the third argument is an uninstantiated variable, represented by _G368
   Call: (7) _G444 is 2+ -1 ? creep
      % the first goal in this claus is "Y1 is Y -1", which is here
      % translated with its bindings
   Exit: (7) 1 is 2+ -1 ? creep
      % the is/2 goal has been called, and has provided a binding for "Y1"
   Call: (7) pow(2, 1, _G443) ? creep
      % this is the first recursive call, with the new arguments 2, 1 and an
      % undefined Z1
   Call: (8) _G447 is 1+ -1 ? creep
      % again the second clause is used, this is the first goal in it,
      % calling is/2
   Exit: (8) 0 is 1+ -1 ? creep
      % is/2 delivers a binding for the current Y1, 0
   Call: (8) pow(2, 0, _G446) ? creep
      % the next (second) recursive call; see how at this point non of the
      % "Z is Z1*X" "statements" have been reached
   Exit: (8) pow(2, 0, 1) ? creep
      % the second recursive call matches the first clause; this is where
      % the base case is used! it can immediately "Exit" as with the match
      % to the clause all bindings have been established already; the third
      % argument is instantiated to 1
   Call: (8) _G450 is 1*2 ? creep
      % now the recursion has terminated, and control is passed back to that
      % more recent calling clause (this was the one where Y1 has been bound
      % to 0); now the "Z is Z1*X" can be tried for the first time, and Z
      % can be instantiated ("unified")
   Exit: (8) 2 is 1*2 ? creep
      % this is the result of this unification, Z is bound to 2;
      % with this, this level in the stack of recursive calls has been completed...
   Exit: (7) pow(2, 1, 2) ? creep
      % ... and this is the result ("Exit") of this call, showing all
      % instantiated parameters
   Call: (7) _G368 is 2*2 ? creep
      % but this just brings us back one more level in the call stack, to a
      % pending execution (this was the one where Y1 has been bound to 1),
      % now the pending execution can be performed
   Exit: (7) 4 is 2*2 ? creep
      % here you see the result of the execution of is/2, binding Z to 4
   Exit: (6) pow(2, 2, 4) ? creep
      % and this finishes the initial call of the predicate, delivering a
      % binding for the X in the query, 4; you can tell that the recursive
      % call stack as been processed completely by looking at the "stack
      % depth indicator", (6), which matches the initial (6) when the trace
      % started (they don't necessarily start with 0 or 1).
于 2011-10-18T13:00:39.650 回答