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

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 2

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.