Search code examples
prologfactorial

Recursive procedure explanation

So I have the following working code in Prolog that produces the factorial of a given value of A:

factorial(0,1).
factorial(A,B) :- A>0, C is A-1, factorial(C,D), B is A*D.

I am looking for an explanation as to how this code works. I.e, what exactly happens when you ask the query: factorial(4, Answer).

Firstly,

factorial(0, 1).

I know the above is the "base case" of the recursive definition. What I am not sure of why/how it is the base case. My guess is that factorial(0, 1) inserts some structure containing (0, 1) as a member of "factorial". If so, what does the structure look like? I know if we say something like "rainy(seattle).", this means that Seattle is rainy. But "factorial(0, 1)"... 0, 1 is factorial? I realize it means factorial of 0 is 1, but how is this being used in the long run? (Writing this is helping me understand more as I go along, but I would like some feedback to make sure my thinking is correct.)

factorial(A,B) :- A>0, C is A-1, factorial(C,D), B is A*D.

Now, what exactly does the above code mean. How should I read it?

I am reading it as: factorial of (A, B) is true if A>0, C is A-1, factorial(C, D), B is A*D. That does not sound quite right to me... Is it?

"A > 0". So if A is equal to 0, what happens? It must not return at this point, or else the base case would never be used. So my guess is that A > 0 returns false, but the other functions are executed one last time. Did recursion stop because it reached the base case, or because A was not greater than 0? Or a combination of both? At what point is the base case used?

I guess that boils down to the question: What is the purpose of having both a base case and A > 0?

Sorry for the badly formed questions, thank you.

EDIT: In fact, I removed "A > 0" from the procedure and the code still works. So I guess my questions were not stupid at least. (And that code was taken from a tutorial.)

Solution

  • It is counterproductive to think of Prolog facts and rules in terms of data structures. When you write factorial(0, 1). you assert a fact to the Prolog interpreter that is assumed to be universally true. With this fact alone Prolog can answer questions of three types:

    • What is the factorial of 0? (i.e. factorial(0, X); the answer is X=1)
    • A factorial of what number is 1? (i.e. factorial(X,1); the answer is X=0)
    • Is it true that a factorial of 0 is 1? (i.e. factorial(0,1); the answer is "Yes")

    As far as the rest of your Prolog program is concerned, only the first question is important. That is the question that the second clause of your factorial/2 rule will be asking at the end of evaluating a factorial.

    The second rule uses comma operator, which is Prolog's way of saying "and". Your interpretation can be rewritten in terms of variables A and B like this:

    B is a factorial of A when A>0, and C is set to A-1, and D is set to the factorial of C, and B is set to A times D

    This rule covers all As above zero. The reference to factorial(C,D) will use the same rule again and again, until C arrives to zero. This is when this rule stops being applicable, so Prolog would grab the "base case" rule, and use 1 as its output. At this point, the chain of evaluating factorial(C, D) starts unwrapping, until it goes all the way to the initial invocation of the rule. This is when Prolog computes the final answer, and factorial/2 returns "Yes" and produces the desired output value.

    In response to your edit, removing the A>0 is not dangerous only for getting the first result. Generally, you can ask Prolog to find you more results. This is when the factorial/2 with A>0 removed would fail spectacularly, because it would start going down the invocation chain of the second clause with negative numbers - a chain of calls that will end in numeric overflow or stack overflow, whichever comes first.