JS ES6 Recursive Tail Call Optimization

What is tail call optimization? Well it’s when the interpreter realizes that the last thing a function needs to do before it’s returned is evaluate a function invocation inside of it. When this beautiful moment happens tail call optimization may occur. Fun stuff, right?!

Lets back up a little bit, Sparky, so we’re all clear on a few things before we go any further. When you declare a function it’s added to global memory, and when you invoke that function a few things will happen. First, the location to return to is saved on the call stack inside a new stack frame. Second, the interpreter will jump inside the function’s new execution context. And lastly, any parameters will be initialized within the function’s local variable environment.

The part we care about, however, is the call stack. The call stack takes up space, and if you push too many functions onto the call stack before it can pop them off you’ll ultimately get a ‘Maximum call stack size exceeded’ error painted in a pretty red color across your console. Fun stuff (not). And with recursion you’re quite susceptible to this error mostly due to having a bad base case, because your logic is off somehow. On the off chance that your base case logic is actually sound, then it means that your function simply requires too many recursive calls before it can even reach the base case.

So, how do we go about optimizing this? Well, tail call optimization is one road, and it’s the one we’re going to be talking about today.

For an example lets start with Math.pow(). Here’s a simple rewrite of Math.pow() with recursion:

function pow(base, power) {
if (power === 0) return 1;
else
return pow(base, power - 1) * base; //tail call === false
}

With our current implementation we’ll be creating a new stack frame each time we recursively call pow() until our base case is reached. So, you can imagine if I do this:

pow(4, 84599); //bad idea

I got ‘that’ error. As expected…

So, how do we got about using tail call optimization to not receive ‘that’ error? Well, we’ll want to remove any unnecessary references to local variables in the return statement. See that ‘* base’(pretty star, that one), we’re going to want to get rid of that. Or say for for the fibonacci sequence we have:

return fib(n - 1) + fib(n - 2);

Get rid of that extra function invocation.

What’s the why in both cases? Well, in scenario one we’re doing an arithmetic operation (multiplication) which is using a local variable as part of the expression which would require a new stack frame each time, because we need to keep a reference to each unique ‘base’ variable to perform the operation properly. For scenario two, we’re making stack frames reliant on each other. Both the first and second function need to be evaluated before we can return anything, and this is no good for what we’re trying to achieve.

So, how do we fix this? For pow() it would look something like this:

function pow(base, power) {
if (power <= 0) return 1;

return helper(base, power, base); //tail call === true
}
function helper(base, power, num) {
if (power === 1) return num;
else return helper(base, power - 1, base * num);
}

See how we’re not using that local variable anymore? Now, we have a simple return in where the last thing being evaluated before the function returns is a function invocation, and that is exactly what tail call optimization is.

Now for fib():

return fib(n-1, a + b, a); 

Okay, so I didn’t do fib(). You get the point though.

Behind the scenes what tail call optimization is doing is simple. Instead of creating a new stack frame for each recursive call, it’s rewriting over the same stack frame which would convert your O(n) space to O(1) space. It can do this, because each recursive call is no longer depending on other recursive calls to finish, nor is it relying on storing local variables in each unique context.

With all of this being said, you might be wondering if tail call optimization is only used for recursion… short answer, it’s not. Go ahead and check out http://www.2ality.com/2015/06/tail-call-optimization.html for a more detailed explanation as to how you determine the tail position of something, and more!

Note: You have to use strict mode to have access to tail call optimization!

Thanks for reading, and I hope you enjoyed! Cheers!