# Recursive Functions using a Trampoline in JavaScript

An interesting technique for managing perceived tail-call optimised algorithms in an environment that does not provide such capabilities is to use a concept called a ‘trampoline’. The following two examples provide all their work within the recursive function invocation and are in tail-call position. However in environments without such optimisations (before ES2015), a single stack-frame is not reused and instead has the pain of O(n) memory complexity.

## Odd and Even

The mutually recursive implementation documented below is a trivial manner in which to calculate if a given value is odd or even. It should be noted that modulo arithmetic would be a more performant approach, but would not highlight the issue at hand.

```
const odd = (n) => n === 0 ? false : even(n - 1);
const even = (n) => n === 0 ? true : odd(n - 1);
odd(100000);
// RangeError: Maximum call stack size exceeded
```

As you can see we sadly hit the call stack size with a sufficiently sized value. However, with a technique called ‘trampolining’ we are able to return to the desired single call stack frame, with the larger heap taking the load.

```
const trampoline = (fn) => {
while (typeof fn === 'function') {
fn = fn();
}
return fn;
};
```

The above implementation does not handle the use-case that the desired returned value is a function itself. This can be easily addressed however with a more advanced implementation, of which I will write about in a future article.

```
const odd = (n) => () => n === 0 ? false : even(n - 1);
const even = (n) => () => n === 0 ? true : odd(n - 1);
trampoline(odd(100000));
```

Simply by wrapping the two recursive calls in functions we are able to supply the initial call to the trampoline function and enjoy the fruits of our labor.

## Factorial

Another example of which could be deemed tail-call optimised is the factorial implementation documented below.

```
const factorial = (n, acc = 1) => (n < 2) ? acc : factorial(n - 1, n * acc);
// factorial(100000);
// RangeError: Maximum call stack size exceeded
```

However, this is similarly not the case - but with a little function wrapper addition and invocation via the ‘trampoline’ method we are able to maintain the succinct manner of the algorithm whilst gaining the single stack-frame. The only point to note is a computational result such as this will require the concept of a BigInt to achieve.

```
const factorial = (n, acc = 1) => () => (n < 2) ? acc : factorial(n - 1, n * acc);
trampoline(factorial(100000)) // BigInt required
```