递归在序言

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想象成一个函数，它被分成了两个处理不同参数值的子句。该函数是递归的，这是由第二个子句中的递归调用触发的。但是在这次通话之后，还有一些事情要做，即目标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 2

与星号（*）的跟踪每一行使用 “Z是Z1 * X” 的规则。

此代码的工作通过提供功率函数的以下递归定义：

1. X^0 = 1对于所有X.
2. X^Y = X ^（Y-1）* X

Z，Z1和Y1变量是Prolog需要一种方式来引用中间结果的事实的假象;你叫Y-1 Y1，你叫X ^（Y-1）Z1。

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

Answer 3

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

何时达到第一个条款？每次都尝试过。但是除非第二个参数是0并且第三个参数是1（或者它们是可以与这些值统一的变量），否则它会失败。当第一个条款失败时，第二个条款被尝试。