1

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

Improve this question
1
  • btw, your pow is missing cut in first clause. The way it is written it would fall into infinite recursion if you instruct prolog to try to find more solutions after the first one is found. Commented Oct 18, 2011 at 6:39

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks a lot, but I realized my main problem is understanding when the last argument is reached (Z). Can you elaborate on that?
Say you enter something like pow(2,3,Res). The first clause is clearly false (3 != 0). When the second clause is tried, first the variable Y1 is computed. Then pow is used recursively, assigning value to Z1. Last, the value of Z is computed.
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).
Improve this answer

2 Comments

I think I understand, but something that is still a little bit unclear, why does _G446 instantiate to 1? Because there the other two parameters match the fact, and the last parameter '_G446' is uninstantiated? If so, then I understand! Thanks again for the explanation
"Because there the other two parameters match the fact, and the last parameter '_G446' is uninstantiated?" - Exactly.
1

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.

Improve this answer

2 Comments

How about the last parameter in the base case? pow(_,0,1). I understand the first parameter is anonymous, so we dont care about it, the second parameter is obvious, but I dont understand how the '1' is reached. Thanks!
pow(X,0,1) is a fact. It means that whatever X you take to the power of 0 yields 1. if you only use that fact you can ask prolog questions like: pow(48,0,X). and it will answer that X = 1

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.