Prolog factorial recursion

Question

I'm having trouble understanding the following factorial program

fact1(0,Result) :-
    Result is 1.
fact1(N,Result) :-
    N > 0,
    N1 is N-1,
    fact1(N1,Result1),
    Result is Result1*N.

When fact1 is called nested within the second fact1, doesn't that mean that the the last line, Result is Result1*N., is never called? Or in Prolog does the last line get executed before the recursive call?

Answer 1

No, the recursive call happens first! It has to, or else that last clause is meaningless. The algorithm breaks down to:

factorial(0) => 1
factorial(n) => factorial(n-1) * n;

As you can see, you need to calculate the result of the recursion before multiplying in order to return a correct value!

Your prolog implementation probably has a way to enable tracing, which would let you see the whole algorithm running. That might help you out.

Answer 2

BTW once you got the basic recursion understood, try to achieve tail recursion whenever possible, here it'd be:

factorial(N, R) :- factorial(N, 1, R).
factorial(0, R, R) :- !.
factorial(N, Acc, R) :-
    NewN is N - 1,
    NewAcc is Acc * N,
    factorial(NewN, NewAcc, R).

Tail recursion, unlike the recursion you used previously, allows interpreter/compiler to flush context when going on to the next step of recursion. So let's say you calculate factorial(1000), your version will maintain 1000 contexts while mine will only maintain 1. That means that your version will eventually not calculate the desired result but just crash on an Out of call stack memory error.

You can read more about it on wikipedia.

Answer 3

Generally speaking, @m09's answer is basically right about the importance of tail-recursion.

For big N, calculating the product differently wins! Think "binary tree", not "linear list"...

Let's try both ways and compare the runtimes. First, @m09's factorial/2:

?- time((factorial(100000,_),false)).
% 200,004 inferences, 1.606 CPU in 1.606 seconds (100% CPU, 124513 Lips)
false.

Next, we do it tree-style—using meta-predicate reduce/3 together with lambda expressions:

?- time((numlist(1,100000,Xs),reduce(\X^Y^XY^(XY is X*Y),Xs,_),false)).
% 1,300,042 inferences, 0.264 CPU in 0.264 seconds (100% CPU, 4922402 Lips)
false.

Last, let's define and use dedicated auxiliary predicate x_y_product/3:

x_y_product(X, Y, XY) :- XY is X*Y.

What's to gain? Let's ask the stopwatch!

?- time((numlist(1,100000,Xs),reduce(x_y_product,Xs,_),false)).
% 500,050 inferences, 0.094 CPU in 0.094 seconds (100% CPU, 5325635 Lips)
false.

Answer 4

factorial(1, 1).
factorial(N, Result) :- M is N - 1,
factorial(M, NextResult), Result is NextResult * N.

Answer 5

Base case is declared. The conditions that N must be positive and multiply with previous term.

 factorial(0, 1).
 factorial(N, F) :- 
       N > 0, 
       Prev is N -1, 
       factorial(Prev, R), 
       F is R * N.

To run:

factorial(-1,X).

Answer 6

A simple way :

 factorial(N, F):- N<2, F=1.

 factorial(N, F) :- 
     M is N-1, 
     factorial(M,T), 
     F is N*T.

Answer 7

I would do something like:

fact(0, 1).
fact(N, Result):-
    Next is N - 1,
    fact(Next, Recursion),
    Result is N * Recursion.

And a tail version would be like:

tail_fact(0, 1, 0).         /* when trying to calc factorial of zero */
tail_fact(0, Acc, Res):-    /* Base case of recursion, when reaches zero return Acc */
     Res is Acc.
tail_fact(N, Acc, Res):-    /* calculated value so far always goes to Acc */
     NewAcc is N * Acc,
     NewN is N - 1,
     tail_fact(NewN, NewAcc, Res).

So for you to call the:

non-tail recursive method: fact(3, Result).

tail recursive method: tail_fact(3, 1, Result).

This might help ;)

Answer 8

non-tailer recursion :

 fact(0,1):-!. 
   fact(X,Y):- Z=X-1,
         fact(Z,NZ),Y=NZ*X.

tailer recursion:

fact(X,F):- X>=0,fact_aux(X,F,1).
fact_aux(0,F,F):-!.
   fact_aux(X,F,Acc):- 
       NAcc=Acc*X, NX=X-1, 
    fact_aux(NX,F,NAcc).