遞歸在序言

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（或者它們是可以與這些值統一的變量），否則它會失敗。當第一個條款失敗時，第二個條款被嘗試。