1 Presentation of Prolog
  1.1 What is a Prolog program
      1.1.1 The Program
      1.1.2 The Query

2 The Facts
  2.1 Simple facts
  2.2 Facts with arguments
  2.3 How to query

3 Variables and Unification
  3.1 Simple unifications
  3.2 Variables unification example

4 Rules
  4.1 Rules
  4.2 How to add a rule with a program
      4.2.1 The instructions
      4.2.2 Example

5 Backtracking
  5.1 Fail
  5.2 Cut
  5.3 Not

6 Recursion
  6.1 What is recursion
  6.2 Examples of Recursion
      6.2.1 Example of the ancestors
      6.2.2 Factorial

7 Lists
  7.1 What is a list in Prolog
  7.2 How to manipulate list

8 Others Elements of Prolog
  8.1 Operators
  8.2 Arithmetic

9 Input and Output
  9.1 Input Output commands
  9.2 Read and Write
  9.3 Examples
      9.3.1 Calculating the cube of an integer
      9.3.2 Treating the terms of a file
      9.3.3 ASCII characters
      9.3.4 Using Another Program

10 SWI-Prolog
  10.1 What is SWI-Prolog
  10.2 Author
  10.3 Platforms
  10.4 FTP Sites


A Meta Logical Constructs

B Input and Output
  B.1 input
  B.2 Output

C Some Others usefull predicats
  C.1 True
  C.2 Repeat
  C.3 Call
  C.4 Setof
  C.5 Bagof

D Comparison Operators
  D.1 Arithmetic Comparison Operators
  D.2 Term Comparison

This Report in LaTeX
About us

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),

     /* 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(X,Y) :-
                      X1 is X - 1,
                      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
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.

Lists -->