Tips on Writing Recursive Procedures in Prolog

The Basics - Base Case and Recursive Case(s)

When writing a recursive procedure in Prolog, there will always be at least two rules to code: at least one rule for the base case, or non-recursive case, and at least one rule for the recursive case.

The Base Case

Typically the base-case rule(s) will deal with the smallest possible example(s) of the problem that you are trying to solve - a list with no members, or just one member, for example. If you are working with a tree structure, the base case might deal with an empty tree, or a tree with just one node in it (like tree(empty, a, empty)).

The Recursive Case

To write the recursive case rule(s), you need to think of how the current case of the problem could be solved assuming you had already solved it for all smaller cases. For example, if you were adding a list of 10 numbers, and you had a way of summing the last 9 numbers in the list, then you would do so, then add on the first number on the list. (It might seem more natural to add up the first 9 numbers and then add the last number to the subtotal, but in Prolog it is easy to access the first item in the list, but not the last.)

Example 1: adding up a list of numbers

Here's an example of how to apply this to adding up a list of numbers. The comments beginning %% would not normally appear - they are there this time to help you match the scheme described in the previous paragraphs to the code.

% addup(List, Sum)
% Binds Sum to the sum of the numbers in the list.
% Assumes that each member of the list really is a number.
% The List must be instantiated at the time addup is called.
% Example of use:
% addup([1,2,3,4], X)?
% X = 10

%% base case
addup([], 0). % sum of the empty list of numbers is zero

%% recursive case: if the base-case rule does not match, this one must:
addup([FirstNumber | RestOfList], Total) :-
	addup(RestOfList, TotalOfRest),   % add up the numbers in RestOfList
	Total is FirstNumber + TotalOfRest.

Example 2: finding the last item of a list

This example shows how to find the last item in a list:

% lastitem(List, Last)
% Binds Last to the item at the end of List.
% List must be instantiated at the time of call, and must not be empty.
% Example of use:
% lastitem([a,b,c,d], X)?
% X = d

%% base case: list with just one item.
lastitem([OnlyOne], OnlyOne).

%% recursive case: ignore first item, seek last item of rest of list
lastitem([First | Rest], Last) :-
	lastitem(Rest, Last).

Example 3: Squaring each item in a list of numbers

This example shows how to build a result that is a list, i.e. we are transforming a list to produce a new list.

This time we'll start with a version with bugs (= errors) in it and also a stylistic error, and then we'll correct the errors. With each version of the code, you should look carefully at it before reading on, and try to spot the bug (or stylistic error). Spotting the bugs and stylistic errors is something you will have to do for yourself when you write your own programs, so start on it now!

NB: square_1, square_2, square_3, and square_4 are all wrong. Only square_5 is correct.

For the sake of brevity in this exposition, I've left out the comments in all but the final version. In practice you would develop the comments as you wrote the code. However, remember that just because you say something is true about the code, in your comments, doesn't mean it is. And don't forget to review and if necessary correct your comments when you find and fix a bug.

square_1([First | Rest], [First * First | SquareRest]) :-
	square_1(Rest, SquareRest).
Try it out:
: square_1([1, 3, 5], Squares)?
** no

Oops - we left out the base case. If you turn on tracing before you execute the query above, you will be able to see 1 * 1, 3 * 3, and 5 * 5 being produced, but because there is no base case, Prolog cannot complete the query.

square_2([], []).
square_2([First | Rest], [First * First | SquareRest]) :-
        square_2(Rest, SquareRest).
Try it out again:
: square_2([1, 3, 5], Squares)?
Squares = [1 * 1, 3 * 3, 5 * 5]

That's better, but why didn't it work out that 1 * 1 = 1, 3 * 3 = 9, etc.?
Answer: because we didn't ask it to. In Prolog, in most cases, evaluation of an arithmetic expression must be explicitly called for using the built-in predicate is.

square_3([], []).  
square_3([First | Rest], [Square | SquareRest]) :-
        FirstSquared is First * First,
        square_3(Rest, SquareRest),
        Square = FirstSquared.
Try it:
: square_3([1, 3, 5], Squares)?
Squares = [1, 9, 25]

Whee! It works. But it contains a stylistic problem. The final goal Square = FirstSquared is redundant - it can be done better by simply writing FirstSquared instead of Square in the head of the rule:

square_4([], []).  
square_4([First | Rest], [Firstsquared | SquareRest]) :-
        FirstSquared is First * First,
        square_4(Rest, SquareRest).
Always try it out after any change:
: square_4([1, 3, 5], Squares)?
Squares = [_R36, _R55, _R74]

Say what? Why doesn't it work any more? Oh. We mistyped FirstSquared as Firstsquared in the head of the rule. Prolog cares desperately about upper and lower case letters, and the "s" of Squared is lower case in the head of the rule, but upper case in the first goal of the body. This can lead to a range of mystifying error messages - the type above, with one or more unresolved _R… variables, is one possibility.

%% base case
% nothing to square; result is empty list.
square_5([], []).  
%% recursive case
% square the First item, recursively square the Rest. 
square_5([First | Rest], [FirstSquared | SquareRest]) :-
        FirstSquared is First * First,
        square_5(Rest, SquareRest).
Always try it out - even if you just added comments, in case you forgot to put a % sign at the front of a comment line.
: sqare_5([1, 3, 5], Squares)?

ERROR: Undefined predicate.
In:      sqare_5([1, 3, 5], _R15) ?
What NOW!!!??? Oh. We mis-typed square_5 as sqare_5 in the query.
: square_5([1, 3, 5], Squares)?
Squares = [1, 9, 25]
© Bill Wilson, 2004-2005
Bill Wilson's contact info

UNSW's CRICOS Provider No. is 00098G
Last updated: