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

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