Search code examples
recursionprologfactorial

Prolog factorial recursion

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?

Solution

  • 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.