Prolog factorial recursion

Prolog factorial recursion

BTW once you got the basic recursion understood, try to achieve tail recursion whenever possible, here itd 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 lets 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.

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.

Prolog factorial recursion

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

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

Lets try both ways and compare the runtimes. First, @m09s 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 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, lets define and use dedicated auxiliary predicate x_y_product/3:

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

Whats to gain? Lets 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.

Leave a Reply

Your email address will not be published.