## Bug in version of `factorial`

Here is the code with the bug.

% Version of factorial(N, FactorialN) with a bug in it.
factorial(0, 1).
factorial(N, Result) :-
write("Entering recursive rule for factorial with N = "), write(N), nl,
Nminus1 is N - 1,
factorial(Nminus1, Nminus1Factorial),
Result is N * Nminus1Factorial.

The challenge was:

Try copying and pasting this code into Prolog, and then typing the
goal `factorial(5, Result)?`

and see what happens. Can you
figure out the bug?

When you run this query, it first computes the correct answer, then
backtracks and looks for further solutions. This leads it to try computing
factorial(-1), factorial(-2), ... and so on for ever, or in fact until
the Prolog interpreter runs out of memory.

There are a couple of ways at least to fix the bug. You can either change
the first rule to:

factorial(0, 1) :- !.

which explicitly says "don't backtrack after you've found the answer!",
or you can change the second, recursive rule to:

factorial(N, Result) :-
write("Entering recursive rule for factorial with N = "), write(N), nl,
N > 0,
Nminus1 is N - 1,
factorial(Nminus1, Nminus1Factorial),
Result is N * Nminus1Factorial.

which stops to second rule in its tracks if N is 0 (or less).
The first solution is more efficient, but doesn't solve the problem
if factorial is called with a negative argument because of a bug
in the calling program (or because the user makes a mistake, typing
the goal `factorial(-17, N)?`

, for instance. The second
solution involves a (small) extra test each time the recursive rule
is called, but it ensures correctness.

School of Computer Science & Engineering

The University of New South Wales

Sydney 2052, AUSTRALIA

Email: billw at cse.unsw.edu.au

Phone: +61 2 9385 6876

Fax: +61 2 9385 5995

UNSW's CRICOS Provider No. is 00098G

Last updated: