Recursion in prolog

Question

I dont think I understand how recursion works in prolog

The following code (a power function)

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

Creates the following trace:

[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

I dont understand how the last state : 'Z is Z1*X' works. When is this function called? When the base case is reached? How does the base case ever get called?

Thanks

Answer 1

You can think of pow as a function that is split in two clauses that deal with different parameter values. The function is recursive, which is triggered by the recursive call in the second clause. But after this call, there is still something to do, the Z is Z1*1 goal. These "dangling" computations are done when the recursion has terminated and control "bubbles" upward again, on the way back so to speak. (There is a name for this kind of recursion which I can't remember).

Look at this commented trace:

[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

The main point is that pow is not a function. It's a predicate. Prolog doesn't really evaluate pow, it tries satisfy its conditions.

And when is the first clause reached? It's tried every time. But unless the second argument is 0 and the third one is 1 (or they are variables that can be unified with those values), it fails. And when the first clause fails, the second one is tried.

Answer 3

Every line in the trace with the asterisk (*) is using the "Z is Z1 * X" rule.

This code works by providing the following recursive definition of the power function:

1. X^0 = 1 for all X.
2. X^Y = X^(Y-1) * X

The Z, Z1 and Y1 variables are artifacts of the fact that Prolog needs a way to refer to intermediate results; you call Y-1 Y1 and you call X^(Y-1) Z1.

This gets to the base case by decreasing the exponent (Y) by one (yielding Y1) at each level of the recursion until Y = 0 and the first case of the definition applies.