6 Recursion
6.1 What is recursion
The recursion in any language is a function that can call itself until the goal has been succeed.In Prolog, recursion appears when a predicate contain a goal that refers to itself.
As we have seen in the earlier chapters when a rule is called Prolog create a new query with new variables. So it make no difference wether a rule calls another rule or call itself.
In Prolog and in any language, a recursive definition always has at least two parts. A first fact that act like a stopping condition and a rule that call itsefl simplified. At each level the first fact is checked. If the fact is true then the recursion ends. If not the recursion continue.
A recursive rule must never call itself with the sames arguments ! If that happens then the program will never end.
6.2 Examples of Recursion
6.2.1 Example of the ancestors
parent(john,paul). /* paul is john's parent */
parent(paul,tom). /* tom is paul's parent */
parent(tom,mary). /* mary is tom's parent */
ancestor(X,Y) :- parent(X,Y).
/* If Y is a parent of X, then Y is an ancestor of X */
ancestor(X,Y) :- parent(X,Z),
ancestor(Z,Y).
/* if Y is an ancestor of Z and Z is a parent of X,
then Y is an ancestor of X */
This program finds ancestors using the database at the begin of the program using the recursive rule of ancestor. If now we ask to Prolog :
?- ancestor(john,tom).
Prolog will first look in the program what he can fint about ancestor. He'll try the goal parent(john,tom). and it will fail. It will now try the second clause of ancestor. The new query is parent(john,Z). Prolog will find Z=paul and try ancestor(paul,tom) wich will conduct to check parent(paul,tom). This is succesfull. As a result the goal ancestor(paul,tom) succeeds. Then ancestor(john,tom) can succeed.
The execution would be :
CALL ancestor(john,tom).
CALL parent(john,tom).
FAIL parent(john,tom).
CALL parent(john,Z).
TRY Z=paul
CALL ancestor(paul,tom).
CALL parent(paul,tom).
SUCCEEDS parent(paul,tom).
SUCCEEDS ancestor(paul,tom).
SUCCEEDS with Z=paul
SUCCEEDS ancestor(johnmtom).
6.2.2 Factorial
The best way in Prolog to calculate a factorial is to do it recursivelly. Here is an example of how it can be done :
factoriel(0,1).
factoriel(X,Y) :-
X1 is X - 1,
factoriel(X1,Z),
Y is Z*X,!.
Note that in this case the cut is not necessary, it means that there is only one solution. The message ''Out of local stack'' may appear if you press ';' after the first solution.
Now if you enter :
?- factoriel(5,X).
X = 120
Yes
In this example Prolog will try to calculate 5! then 4! then 3! until it has to calculate 0!, then the result will be 0!*1*2*3*4*5. Prolog will respond 120.|
<-- Backtracking
|
-
|
Lists --> |