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.
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