A stack frame-by-frame breakdown of how TCP improves your memory footprint
Every time we call a function, we stack another rock on top. This obviously does not scale.
One of the behind-the-scenes changes that is coming with ES6 is support for tail call optimization (TCO). Tail call optimization means that, if the last expression in a function is a call to another function, then the engine will optimize so that the call stack does not grow. Let’s take a look.
What is Tail Call Optimization?
Tail call optimization means that it is possible to call a function from another function without growing the call stack. In order to understand the importance of that statement, we have to talk about how the stack works.
You might be familiar with the word stack considering it is one of the most commonly seen data structures. It is a LIFO (last-in first-out) queue with two primary operators — push and pop. The “call stack” is an implementation of the stack data structure used to navigate a program through function calls and store variables local to those functions. Consider the following code block:
(function wrapperFunction(){ console.log("Executing in the Wrapper Function");
function functionA(a,b,c) { console.log("Executing in Function A"); functionC(10,11); return; }
function functionB(d,e,f) { console.log("Executing in Function B"); return; }
function functionC(g,h) { console.log("Executing in Function C"); return; }
functionA(20, 40, 60); functionB(15, 25, 35); functionC(17, 22, 27);})();
The output of the above block of code is
Executing in the Wrapper FunctionExecuting in Function AExecuting in Function CExecuting in Function BExecuting in Function C
What we have here are a series of function calls nested within one another. During runtime, when the javascript engine sees the immediately-invoked function expression (IIFE) titled wrapperFunction, it pushes a frame to the call stack which includes the parameters, a return address, and all variables currently in scope. That being said, our first frame of the call stack includes the return address to the global execution, the variables which are in scope, which, at this point, are none, and all variables passed into the function (also none).
When we then call functionA later on, the engine will push the call to functionA to the stack. This frame will now include the return address back to the current location in wrapperFunction and the values 20, 40, and 60 to be stored in references a, b, and c, respectively.
This process happens for every function call. If you look at the image below and read it from left to right, you can see this process happening. We begin by pushing the wrapperFunction call on top of the global execution frame. Then, functionA gets called and pushed onto the stack, followed by functionC which is called by functionA. Observe that you can tell which function is currently executing by looking at the top of the call stack and see which function called it by seeing which frame is below it. This is known as the stack trace of the function execution.
The diagram represents the call stack of the code block above from left to right
The diagram represents the call stack of the code block above from left to right (click to enlarge)
So that brings us back to our original question: What is tail call optimization? The best example of a tail call is a recursive function. We know that a recursive function is one that calls itself, but what makes it a tail call? A tail recursive function is one that can get rid of its frame on the call stack after recursively calling itself.
Example: Fibonacci Sequence
The easiest way to tell that a function exhibits tail recursion is by looking at the return statement in a function that calls itself. If the return statement of the recursive function is a call to itself, i.e return recursiveFunction() and nothing else, then the javascript engine will be able to optimize the tail call and not grow the stack.
As an example, we will create a function that calculate a Fibonacci number. The N’th Fibonacci number is the sum of the numbers at N-1 and N-2 in the same sequence with the first two numbers both being 1.
1, 1, 2, 3, 5, 8, 13, 21, ..., N-2, N-1, N
The Fibonacci sequence up to the N’th digit
Let’s think about how we could calculate the numbers above programatically. We know that a Fibonacci number is the sum of the previous two numbers, each of which are the sum of the two numbers that precede them, respectively. That being said, if we want to calculate the N’th Fibonacci number, we begin with the first number, 1, and an initial sum of 0 (which we leverage default parameters to set) and then iterate through that summing process N number of times.
(function(){ function fib(n, sum=0, prev=1) { if (n <= 1) return sum; return fib(n-1, prev+sum, sum); } console.log(fib(20000));})();
The above is a tail recursive function. It does not need to hold onto its stack frame
This might seem a little hard to follow, but it is really quite simple. fib is nothing more than a function that adds two numbers and then passes through that sum (to be used as the next N-1) to the next iteration, along with the number it just added (the next N-2) and the number of iterations left to run.
It is tail recursive because the return statement consists solely of a call to itself, passing along all information that it needs with it. Therefore, the javascript engine optimized for tail recursion can dump that frame before pushing on the new one.
Example 2: Non-tail Fibonacci Sequence
To contrast the above example, let’s consider another implementation of the Fibonacci sequence, this time without using a tail recursive method.
It was stated above that the N’th Fibonacci number is the sum of the fibonacci numbers at N-1 and N-2. Therefore, we can also implement it as the following:
function fib(n) { if (n <= 0) return 0; if (n === 1 || n === 2) return 1; return fib(n-1) + fib(n-2);}console.log(fib(20000)); //ERROR: maximum call stack size exceeded
This is NOT a tail recursive function. It must hold a stack frame for each call.
This function has calls to itself in the return statement, HOWEVER, it contains two of them in an addition statement. Therefore, as was the case in the very first example of this post, it needs to maintain a reference to state of the original calling function for every single iteration it goes through so it knows which two results to add.
With that in mind, do not run this function in a console unless you want to crash it and, more importantly, do not write recursive functions that are not tail recursive.
Example 3: Non-Recursive Tail Optimization
TCO is not just for recursive functions. Any function that ends with an invocation of a function can be optimized. Let’s return to the first example of the post and change the invocation of functionC within functionA to be a tail call.
(function wrapperFunction(){
console.log("Executing in the Wrapper Function");
function functionA(a,b,c) { console.log("Executing in Function A"); return functionC(10,11); //Now a tail-call }
function functionB(d,e,f) { console.log("Executing in Function B"); return; }
function functionC(g,h) { console.log("Executing in Function C"); return; }
functionA(20, 40, 60); functionB(15, 25, 35); functionC(17, 22, 27);})();
The invocation of functionC from within functionA is now a tail call
In the example above, the return statement of functionA is a call to functionC. Programmatically, this means that there is no need to return to functionA after the completion of functionC since all we want to do is return the value. Therefore, the optimizer will pop off the functionA frame and push the functionC frame with a return address to wrapperFunction. The return address is the crucial thing to note here. Without TCO, the return address would be functionA, meaning that we would not be able to drop that stack frame. By including the return address to wrapperFunction, however, we can safely drop the functionA frame and the program will run as intended.
The tail call optimizer can drop the functionA stack call frame before pushing functionC
How to Use
In my experience as a javascript developer, it is not TOO often that you have to write recursive functions, but it definitely does happen. So, if you find yourself thinking that you need a recursive function, you should do your best to make it tail recursive. This saves a lot of processing power and prevents the possibility of a stack overflow.
On the other hand, it is very common to have function invocations embedded within other functions. Whenever you see a function with an embedded function invocation, you should consider if it is possible to rearrange the expressions and logic so that you are navigating through the functions using tail calls. This will allow the engine to optimize and drop off unnecessary stack frames, saving processing power and improving performance
Important Notes on Browser/Engine Support
EDIT 5/7/19 — Unfortunately, as far as I know, Safari is the only browser that supports proper tail calls as described in the ES5 specification. I am going to leave this post up, but will be making some edits so that it’s clear this feature is not yet able to be used and might not ever be.