# 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 in1.606seconds (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 in0.264seconds (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 in0.094seconds (100% CPU, 5325635 Lips) false.