序言中的递归

Question

我认为我不明白递归在序言中是如何工作的

以下代码（幂函数）

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 是 Z1*X”是如何工作的。这个函数什么时候被调用？什么时候达到基本情况？ 基本情况是如何被调用的？

谢谢

Answer 1

要点是 pow 不是一个函数。这是一个谓词。 Prolog 并不真正评估pow，它尝试满足其条件。

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

Answer 2

您可以将 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).

Answer 3

跟踪中带有星号 (*) 的每一行都使用“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 称为 X^(Y-1) Z1。

通过在递归的每个级别将指数 (Y) 减一（产生 Y1），直到 Y = 0 并且定义的第一种情况适用，即可得到基本情况。