Walking through the recursive factorial program in Prolog?

Question

I'm really having a hard time understanding how the recursion works in Prolog.

factorial(0,1).   
factorial(N,F) :-  
   N>0, 
   N1 is N-1, 
   factorial(N1,F1), 
   F is N * F1.

I understand the first part is the base case and that would end the continuation of the program. However, the part that confuses me is the parameters of the second factorial call (N1, F1). Can someone explain the steps of how everything is executed and calculated?

Walking though is often not the ideal approach: Rather read the rule right-to-left. Please refer to my previous answers. — false

Tudor Berariu Tudor Berariu · Accepted Answer · 2014-12-06T19:12:36

The second rule basically says that F is the factorial of N if N is greater than zero and there is a number N1 which is the result of N-1 and F1 is the factorial of N1 and F is the product of N and F1.

Example

Let's say that you want to find the factorial of 3.

-? factorial(3,F).

Prolog puts factorial(3,F) on the stack of goals and then looks for rules whose head match the first goal. There are two rules for factorial/2 (the fact factorial(0,1) can be seen as a rule without body), but for the first 0 does not unify with 5 so it cannot be used. The second unifies with N being instantiated to 5 and Prolog adds the conditions to the stack which becomes:

3 > 0, N1 is 3-1, factorial(N1,F1), F is 3*F1

The first goal is satisfied as 3 is greater than zero. The second one is satisfied by binding N1 to the result of the arithmetic evaluation of 3-1 so the stack of goals is now:

factorial(2,F1), F is 3*F1

Again, Prolog looks for rules that might be used to satisfy factorial(2,F1) and uses the second one (N unifies with 2 and F with F1 and different names are used for the variables) :

2 > 0, N2 is 2-1, factorial(N2,F2), F1 is 2*F2, F is 3*F1

Next, 2 > 0 is true and N2 is unified with the arithmetic result of 2-1 so the stack of goals becomes:

factorial(1,F2), F1 is 2*F2, F is 3*F1

Using again the second rule for factorial/2:

1 > 0, N3 is 1-1, factorial(N3,F3), F2 is 1*F3, F1 is 2*F2, F is 3*F1

N3 becomes zero (when N3 is 1-1 is being satisfied):

factorial(0,F3), F2 is 1 * F3, F1 is 2*F2, F is 3*F1

At this point, the first rule for factorial/2 can be used to satisfy factorial(0, F3), but a choice point is created as there are more rules that can be used. So, factorial(0,F3) succeeds by instantiating F3 to 1.

F2 is 1 * 1, F1 is 2 * F2, F is 3 * F3

By satisfying all the goals left on the stack, F becomes 6 and you get your first solution. But, there was a choice point for factorial(0, F3). The second rule can be used at that point:

0>0, N4 is 0-1, factorial(N4,F4), F3 is 0*F4, F2 is 1*F3, F1 is 2*F2, F is 3*F3

But 0>0 fails and the execution stops as there where no other choice points to backtrack to.

You can avoid leaving that useless choice point for factorial(0,_) by using a [green] cut operator.

factorial(0, 1) :- !.

Walking through the recursive factorial program in Prolog?

1 Answers