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 — and . 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: push pop (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 engine sees the immediately-invoked function expression (IIFE) titled , 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). javascript wrapperFunction When we then call later on, the engine will push the call to to the stack. This frame will now include the return address back to the current location in and the values , , and to be stored in references , , and , respectively. functionA functionA wrapperFunction 20 40 60 a b c 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 call on top of the global execution frame. Then, gets called and pushed onto the stack, followed by which is called by . 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. wrapperFunction functionA functionC functionA 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 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 and nothing else, then the javascript engine will be able to optimize the tail call and not grow the stack. recursion return recursiveFunction() 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, , and an initial sum of (which we leverage to set) and then iterate through that summing process N number of times. 1 0 default parameters (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. 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. fib 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 within to be a tail call. functionC functionA (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 from within is now a tail call functionC functionA In the example above, the return statement of is a call to . Programmatically, this means that there is no need to return to after the completion of since all we want to do is return the value. Therefore, the optimizer will pop off the frame and push the frame with a return address to . The return address is the crucial thing to note here. Without TCO, the return address would be , meaning that we would not be able to drop that stack frame. By including the return address to , however, we can safely drop the frame and the program will run as intended. functionA functionC functionA functionC functionA functionC wrapperFunction functionA wrapperFunction functionA The tail call optimizer can drop the stack call frame before pushing functionA 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.
