# JS Drip #65: Don't Blow Your Stack

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.