For some types of programming problems (particularly mathematical problems) the most elegant solution is to use a recursive function, because it directly translates a mathematical definition. Unfortunately, recursive functions in JavaScript can run into trouble quickly.

Suppose that we want to define a recursive function that tells us whether a number is even. (Yes, there are easier ways to determine evenness, we're just exploring recursion.) We might write something like this:

```
function isEvenNaive (num) {
if (num === 0) {
return true;
}
if (num === 1) {
return false;
}
return isEvenNaive(Math.abs(num) - 2);
}
isEvenNaive(10);
// => true
isEvenNaive(9);
// => false
```

The code looks pretty reasonable. But what happens if we use it on a large number, say `99999`

?

```
isEvenNaive(99999);
// => InternalError: too much recursion
```

The exact error varies depending on the JavaScript engine, but at large numbers like these you will eventually hit the call stack depth limit of your engine and have a stack overflow.

The call stack is essentially the in-memory list of all the unresolved function calls, their associated variables, and related information. Each time `isEvenNaive`

is invoked with a value greater than `1`

, it calls itself, adding to the stack and consuming more resources.

Only when we eventually reach the base cases `0`

or `1`

do the recursive function calls resolve, emptying the stack and freeing up resources. Without a limit on recursion depth (or tail call optimization), a deeply recursive function could consume all of your computer's resources.

But recursive functions are really useful. Is there a way that we can write recursive functions that don't overflow the stack? It turns out that there is.

```
function isEvenInner (num) {
if (num === 0) {
return true;
}
if (num === 1) {
return false;
}
return function() {
return isEvenInner(Math.abs(num) - 2);
};
}
isEvenInner(8);
// => function() {
// return isEvenInner(Math.abs(num) - 2);
// };
isEvenInner(8)()()()();
// => true
```

The first thing to notice about our `isEvenInner`

function is that instead of directly calling itself again, it returns an anonymous function. That means each call to `isEvenInner`

gets resolved immediately, **and doesn't increase the size of the stack**. It also means that we need a way to automatically invoke all of those anonymous functions that will get returned along the way. That's where `trampoline`

comes in.

```
function trampoline (func, arg) {
var value = func(arg);
while(typeof value === "function") {
value = value();
}
return value;
}
trampoline(isEvenInner, 99999);
// => false
trampoline(isEvenInner, 99998);
// => true
```

The `trampoline`

function effectively turns this recursive algorithm into something that is executed by a `while`

loop. As long as `isEvenInner`

keeps returning functions, `trampoline`

will keep executing them. When we finally reach a non-function value, `trampoline`

will return the result.

Now we can avoid blowing the stack, but calling `trampoline(isEvenInner, 3)`

isn't that nice. Let's add a little bit of partial application with bind.

```
var isEven = trampoline.bind(null, isEvenInner);
isEven(99999);
// => false
```

It's important to note that while the principles illustrated are widely applicable, this particular implementation of `trampoline`

has some limitations.

- It assumes that you are only passing one argument to the recursive function.
- It assumes that the final returned value will not be a function.
- In some older JavaScript engines
`typeof function`

is inaccurate.

For a more robust implementation, see underscore-contrib.

I hope that this has helped give you a stronger understanding of how recursion works in JavaScript.

Several people have mentioned that they are interested in more intermediate/advanced topics, so I'm working to add more of those into the mix. If you have a topic to suggest, just reply to this email. I love getting feedback.

Thanks for reading!

Josh Clanton