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:
- Some set (or "data structure") over which you are doing the
recursion: common examples include numbers, arrays, trees etc.
- A base case definition, usually dealing with an empty
structure
- 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:
- Data Structure: natural numbers
- Base Case: 0! = 1
- Recursive Case: For any n>0, we have n! = n * (n-1)!
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:
- Data Structure: natural numbers
- Base Case: 0 is even
- Recursive Case: For any n>0 we know that n is even only if
n-2 is even.
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
- Data Structure: section of an array
- Base Case: m>n, in which case the answer is "no"
- Recursive Case: m < n, in which case we say that if
A[m]=E then return "yes", otherwise search between m+1
and n.
Exercise:
- 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 |
- 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:
- Only one disc can be moved at a time
- 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.
- Data Structure: The number of discs to be moved
- Base Case: One disc - To transfer a stack consisting of 1 disc from
peg A to peg B, simply move that disc from A to B
- Recursive Case: To transfer a stack of n discs from A to B, do
the following:
- Transfer the first n-1 discs to some other peg C
- Move the last disc on A to B
- Transfer the n-1 discs from C to peg B
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:
- N is the number of discs to be transferred
- A is the peg on which the discs are stacked
- B is the peg we are to move the discs to
- I is the (empty) intermediate peg to be used for storage
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):
- an object is immediately to the right of another
- an object is immediately to the left of another
- an object is immediately above another
- an object is immediately below another
- an object is exactly between two others, either in a horizontal or
vertical direction
- 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