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: