Prolog Tutorial 3: Recursion

James Power, 1997.


In this tutorial we simply want to practice using recursion. This is really important in Prolog, and we'll be using it a lot from now on, so you should try and work through all of the following...


Using Recursion

In imperative languages like C/C++/Java we deal with situations which require iteration by means of constructs like while, do, for and so on. Prolog does not use these imperative-style constructs: instead, when we need to iterate, we use recursion. Recursion can take a little time to get used to, but it will be used in almost every non-trivial Prolog program from now on.

Basically recursion involves defining something in terms of itself. The key to ensuring that this makes sense is that you always define something in terms of a smaller copy of itself. Recursion is the algorithmic equivalent of "proof by induction" in maths.

When you do recursion you must have three things:

  1. Some set (or "data structure") over which you are doing the recursion: common examples include numbers, arrays, trees etc.
  2. A base case definition, usually dealing with an empty structure
  3. A recursive case definition, explaining how to work out a non-trivial case in terms of some smaller version of itself.

Some Examples

Factorial:
By definition, the factorial of some number n, written n! is n*n-1*n-2* ... *1. We can express this in terms of recursion as follows: Note that we define n! in terms of (n-1)!. This is OK to do, since we know that (n-1) < n

Even:
We do not always have to decrease by 1 each time. For example, we can define a test to see whether a number is even as follows: A similar definition to test if a number is odd would only need to change the base case to refer to 1 rather than 0.

Sequential Search:
Suppose we want to search some section of an array A (say between location m and n) to see if an element E is present

Exercise:

  1. Euclid's algorithm to calculate the greatest common divisor of two numbers can be stated as follows:
    gcd(x,y) = x, when x=y
    gcd(x-y,y), when x>y
    gcd(x,y-x), when y>x
  2. Going back to the family tree example, write a predicate which gives all the direct ancestors of a person i.e. their parents, grandparents, great-grandparents etc. (be sure to use recursion!)


The Towers of Hanoi

This is an old chestnut:

A group of over-proud monks in a Hanoi monastery were assigned a task to perform: they had to move 100 discs from one peg to another with the help of a third peg. There are only two rules:

  1. Only one disc can be moved at a time
  2. The discs are all of different sizes, and no disc can be placed on top of a smaller one
We want to write a Prolog program to solve this; moreover, we suggest that recursion will help us to do this. In fact, posing it as a recursive problem simplifies matters considerably.

Thus, when we wish to transfer n discs we assume that we already know how to transfer n-1 discs.

To see that this works, let's code it in Prolog.

In Prolog...

Since our knowledge of I/O is fairly narrow, we'll just write out the instructions for each move. Let's define a predicate that will write out one instruction:

  % move(A,B) is true if we move the topmost disc from peg A to peg B
  move(A,B) :-
    nl, write('Move topmost disc from '),
    write(A), write(' to '), write(B).

Now to actually do the main work, we'll define a recursive predicate which will have the form transfer(N,A,B,I) where:

Basically, transfer(N,A,B,I) will be satisfied if we can find an algorithm to transfer N discs from A to B using I

Thus we define:

  % transfer(N,A,B,I) is true if we can transfer N discs from A to B
  %                   using I as an intermediate peg.
  % Base case - 1 disc
  transfer(1,A,B,I) :- move(A,B).
  % Recursive case - N discs
  transfer(N,A,B,I) :-
    M is N-1, 
    transfer(M,A,I,B),  % Transfer topmost N-1 discs from A to I
    move(A,B),          % Move biggest disc from A to B
    transfer(M,I,B,A).  % Transfer remaining N-1 discs from I to B

Type this in (save it as hanoi.pl), and try the query:

  transfer(3,peg1,peg2,inter).


The Grid Example

Imagine a grid consisting of (evenly spaced) horizontal and vertical lines; assume that it is possible to place an object at the intersection of any two lines. Suppose also that the lines are potentially infinite in length.

A possible configuration of objects on the grid might be:

         |       |       |       |       |       |    
         |       |       |       |       |       |    
     ----+------[A]-----[B]------+------[C]------+----
         |       |       |       |       |       |    
         |       |       |       |       |       |    
         |       |       |       |       |       |    
     ----+------[D]-----[E]-----[F]-----[G]------+----
         |       |       |       |       |       |    
         |       |       |       |       |       |    
         |       |       |       |       |       |    
     ----+-------+------[H]------+-------+-------+----
         |       |       |       |       |       |    
         |       |       |       |       |       |    
         |       |       |       |       |       |    
     ----+-------+------[I]------+-------+-------+----
         |       |       |       |       |       |    
         |       |       |       |       |       |    

Suggest an appropriate format for a Prolog knowledge base that will represent this. Rather than using absolute co-ordinates (remember - it's infinitely large in theory), describe the position of the objects relative to each other (after all, Prolog is a relational language...)

Think along the lines of the family tree example: make sure that you separate the facts which describe a given situation, from the rules which will work in any situation.

Now write some rules which will check the following (you might already have expressed some of these as facts):

  1. an object is immediately to the right of another
  2. an object is immediately to the left of another
  3. an object is immediately above another
  4. an object is immediately below another
  5. an object is exactly between two others, either in a horizontal or vertical direction
  6. an object is directly beside another in a diagonal direction
Finally, generalise the above so that they return all objects to the right/left or above/below another (using recursion!).


Written by James Power
Released under the GNU Free Documentation License
Last revised: 22 Oct 2006