Evaluating Factorial

Question

I am trying to write a Prolog function to evaluate the factorial of a Number.

factorial(1, 1).
factorial(X, Y) :-
    factorial(A, B),
    Y is B * X,
    A is X-1.

The first bit is the base-case, the factorial of 1 is 1.

It works fine for 1! and 2!, but for any number above that it just throws.

12 ?- factorial(3,X).
ERROR: is/2: Arguments are not sufficiently instantiated

Answer 1

First, your version does not even work for 1 or 2 as you suggest. And there is 0, too. You get answers, but you have not asked for the next answer:

?- factorial(1, F).
   F = 1
;  error(instantiation_error,(is)/2).

So what to do to localize the problem? I will throw in a false:

factorial(1, 1).
factorial(X, Y) :-
    factorial(A, B),
    Y is B * X, false,
    A is X-1.

?- factorial(2, Y).
   error(instantiation_error,(is)/2).

Still same problem. So it must be this very (is)/2 which is the culprit.

Let's pull the false even further:

factorial(1, 1) :- false.
factorial(X, Y) :-
    factorial(A, B), false,
    Y is B * X,
    A is X-1.

There are two remarkable things now: This fragment always loops! And it should be evident why: There is nothing between the head and the recursive goal. Such a situation is called left recursion.

And then there is something else that is remarkable: factorial(A,B) is called with two uninstantiated variables! So add this A is X-1 goal in between, and further ensure that A > 0. And add the case for 0.

Some inevitable ceterum censeo: Consider to learn arithmetics with library(clpfd) instead. (is)/2 is soo 1970s. See the manual for more! See Reversible numerical calculations in Prolog