# BrainFuck part 11 - Iterative and recursive ways

## Tail recursive solution

First solution was definitely iterative : we built N! by building all X! values for X = 1..N

Second solution was defintely recursive : we built N! from the result of (N-1)!

But there is a specific kind of recursive way, called **tail-recursive**. In the previous example, there was a stack of all possible values for N. Although it's pointless when we talk about BF, for other languages it means a virtually very very very long stack of integers, that can lead to some memory issue...

The tail-recursive way is a specific recursion where the call to the sub-problem is the only operation done in the recursive process.

*F(N) = F(N-1) x N*is definitely not tail-recursive*F(N) = N x F(N-1)*isn't, either : after calling F(N-1) there is still a multiplication

It seems impossible to write a tail-recursive definition of factorial, doesn't it?

Actually, it is indeed impossible to define **this exact function F** in a tail-recursive manner. However, we can define another function F':

*F'(N,R) = F'(N-1,R*N)*- F(N) = F'(N,1)

The main advantage of this implementation is that it doesn't add more and more frames to the stack. Instead :

- we have a state (N,R)
- we apply the same method on our state again and again until we reach a given condition
- final state gives us a result

This recursion pattern is often optimized by compilers. It's also a very efficient way to handle recursions in BF

- It doesn't force us to add more and more values on the stack
- It does not need a real "function" or "subroutine" definition: with BF we can easily apply the same method on a given state again and again (as long as a flag is set on our state to indicate whether we should continue or not).

Actually, tail-recursive way can be considered as a recursion implemented with a similar technique than the iterative way: for (state=...;state not final;) state=F(state). But again, the philosophy behind is different : we compute the result based on results for smaller inputs, and not iteratively

## Let's start

- Memory: N 0 0 0 0 0
- Cursor: first cell
- Input: any

## Process

- Set result to 1 (2nd cell)
*invariant: memory is A, B with A! x B = N!*- while A is not null
- decrease A
- copy "A-1"
- multiply B by A-1
- add Bx(A-1) to B to get AxB

- loop
*A = 0, so B = N!*

## Code

```
>+< Set result to 1
[ while A is not null
-[->>+>+<<<]>>>[-<<<+>>>]< decrease and copy A
[-<[->>+>+<<<]>>[-<<+>>]<] get AxB
>>[-<<<+>>>] ** part 2 **
<<<<] loop
```

## Minified version

```
>+<[-[->>+>+<<<]>>>[-<<<+>>>]<[-<[->>+>+<<<]>>[-<<+>>]<]>>[-<<<+>>>]<<<<]
```

## Final state

- Memory: 0 N! 0 0 0 0
- Cursor: first cell
- Input: unchanged
- Output: unchanged

### Test program

This programs prints `x`

, code 120 = 5!

```
+++++>+<[-[->>+>+<<<]>>>[-<<<+>>>]<[-<[->>+>+<<<]>>[-<<+>>]<]>>[-<<<+>>>]<<<<]>.
```