ES6 - From Recursion to Tail Recursion

02.09.2015

The next version of JavaScript (ECMAScript 6) will be introducing an incredibly powerful programming feature called Tail Recursion, a feature that I’m very excited about. In this article I want to talk a bit about recursion vs. iteration, tail recursion and what that means for the future of JavaScript.

Recursion

It has always been a powerful feature inside of JavaScript, and many other programming languages, as a means of solving problems by breaking things down into simpler/smaller versions of themselves. One can think of it in programming context, as a function that calls itself, but with changed or reduced arguments. The recursive strategy of problem solving often times yields quite elegant results, with code that is more readable and clear compared to other approaches, such as brute-forcing or iterating. However, if the task at hand is to drill down through large amounts of nested data, we have a decision to make - recursion or iteration? Let’s start off with some code…

Below is a factorial function, the quintessential recursion example used in many programming languages - nothing too crazy or exciting.

function factorial(n) { return n === 1 ? 1 : n * factorial(n - 1); }

To talk through the function, factorial() simply takes in a numeric argument, say 6, and multiplies the argument by the factorial of the argument subtracted by 1, which then again takes that argument and multiplies it by the factorial of 1, etc., until the argument is 1 and the function returns - alas you have recursion.

The returning of 1 denotes the terminating condition (or base case) required by a recursive function, while the rest of the function continues to execute and recursively call itself until the base case is met. While this simple factorial function may look fine and elegant from a cleanliness perspective, there are some very large implications that go on behind the scenes for how we went about executing our factorial call. A great way to understand how factorial() will go about its execution would be to visualize the stack that is created.

Below you will see a rough representation of what more or less happens behind the scenes when you execute a recursive function in current implementations of JavaScript.

factorial(6) // allocate memory and save state 6 * factorial(5) // allocate memory and save state 6 * (5 * factorial(4)) // allocate mem... 6 * (5 * (4 * factorial(3))) // allocate mem... 6 * (5 * (4 * (3 * factorial(2)))) // allocate mem... 6 * (5 * (4 * (3 * (2 * factorial(1))))) // allocate mem... 6 * (5 * (4 * (3 * (2 * (1 * factorial(0)))))) // allocate mem... (max depth) 6 * (5 * (4 * (3 * (2 * (1 * 1))))) 6 * (5 * (4 * (3 * (2 * 1)))) 6 * (5 * (4 * (3 * 2))) 6 * (5 * (4 * 6)) 6 * (5 * 24) 6 * 120 720

First, we need to get a sense of how this computes in order to understand the space and complexity of memory consumption. Above, we have this recursive cascading tree, where each function call is getting stacked into memory to be allocated for use in the next recursive call. Each recursion takes up space because once we call factorial(6) we are building up deferred operations that are to eventually be performed after the final recursive call completes. There is a rising and falling of space allocated, so for factorial(n) we are allocating n places on the stack. A graphical representation of this memory consumption in relation to recursive call size might look something like the chart below.

From this chart we can declare that memory usage is unbounded (not a good thing). Notice how the memory consumption grows with the addition of each recursive call. Eventually this unbounding increasing of memory will kill our ability to execute as we blow the stack, or what is called a stack overflow. The amount of recursive ability varies depending on browser engine implementations and their respective call stack sizes. One way that we could get a glimpse of the various browsers implementation call stack size limits would be to wrap a recursive call in a try catch, thus catching our limit and preserving our execution, see below.

function count(num) { try { return count((num || 0) + 1); } catch(e) { return num; } }

This function will continue to recurse until the call-stack size exceeds the amount of memory, giving us an estimation of the respective environments call-stack size. Give it a try in various browsers to compare each of their limits.

Iteration

The information above leads us to believe that the use of recursion in JavaScript could be deemed impractical (depending on the needed call stack size), afterall, any algorithm that can be implemented using it can also be implemented using iteration. Let’s see an example of calculating the factorial of a number via iteration versus recursion.

// via Iteration function factorial(n) { if (n === 0) { return 1; } else { var sum = 1; for (var i = 1; i <= n; i++) { sum = sum * i; } return sum; } }

The above, in my opinion, is less elegant and legible than the recursive version declared earlier. It also doesn’t quite utilize the functional aspect of JavaScript that is often considered one of, if not its best, parts of the language. However, an iterative looping approach to the factorial problem would prevent us from adding items to the call stack and thus yielding a bounded consumption of memory.

Anyway, we will pretend that loops are ugly, and recall how we love elegant, clean and readable code, so let’s get back to that slick recursive style. No problem, that means ES6 to the rescue with this great new feature called tail recursion - but first, what exactly is tail recursion?

Tail Recursion ↩ Recursion

So what is tail recursion? Basically, instead of doing an invocation of the recursive function as the return statement (calling a new version of itself), it does a jump and reuses the same context (or activation record) of the prior recursive call, in other words, no added memory cost. What this means is that as we use proper tail recursion in our recursive functions, the memory usage will remain steady rather than continually climbing with each recursive call. For example, a properly implemented tail recursive version of the factorial function’s memory usage might look instead like this.

Compare that to the above chart and we are suddenly much happier programmers. Instead of adding calls to the stack and consuming memory, prior stacks and contexts will be released (or reused) and garbage collected, preventing a continuous growth of memory usage. So all is great and tail recursion is coming to save the day (sort of). Before we get too excited we have to make note of a few caveats. In order to do proper tail recursion, we need to satisfy three things.

be in strict mode
write our programs in proper tail call form
be in a tail call optimized (TCO) environment

The first of those tasks is easy, if you would like to learn more about strict mode check out the MDN resources here. I recommend all JavaScript developers use it.

The second task of proper tail call form is a little trickier. Unfortunately, our previously declared elegant recursive factorial function would not qualify for tail recursion even in a tail call optimized environment. It’s not in proper tail call form, let me explain…

A proper tail call is when the last thing a function does is return the result of calling another function. In the above function the highlighted ternary else returns the result of n * factorial(n - 1), in other words not a standalone function, and as a result would need to retain the stack. An example of a factorial function with proper tail calls (see below), notice the ternary else returns recur(n - 1, n * acc) as a standalone invocation. Note, this properly tail called version of a recursive factorial function is a bit more complicated, however it would qualify for TCO and thus would give us the power of tail recursion.

// via Tail Recursion function factorial(n) { function recur(n, acc) { return n == 0 ? acc : recur(n-1, n*acc); } return recur(n, 1); }

For clarity sake, an overly-simplified example of a non-recursive function in proper tail call form can be seen here. The function below has the possibility for tail call optimization. As soon as foo() executes bar() as its final action, bar() can reuse foo()’s allocated stack rather than adding a new one (and increasing memory usage).

function foo() // do something... return bar(); // proper tail call form }

If we apply our new found recursive memory optimizations to the “real-world”, we might see substantial performance benefits for traversing/handling extremely large data-sets. For the majority of us, the day-to-day JavaScript that we write won’t necessarily benefit from these optimized tail calls. However, let’s say we have a specific problem in front of us that requires the traversal of a massive data tree. A data tree where each node has a substantial amount of information and overhead associated with it - does this sound familiar? Of course it does, it’s the wonderful API that we all know and love, the DOM! As developers, our programs, our bosses, and our clients often require us to interact with the DOM (think tree-traversing algorithm) where performance is paramount. Well now we are better equipped to approach these situations head on.

An example of recursive vs tail recursive implementations of DOM traversal can be found on Guillaume Lathoud’s website here. In the article, Guillaume goes extremely in depth, comparing various performance metrics, e.g. number of recursive calls, stack size, time, etc.., in respect to competing recursive strategies. His article is easily the most thorough write up that I’ve seen on JavaScript tail recursion thus far, and I highly suggest checking it out. Below is a snippet from the article where we create a function that collects all JavaScript files nodes in the DOM, utilizing a recursive approach - recursiveCall(), as well as a tail recursive approach - tailRecursiveCall(). Try and grok the code below…

So we’ve switched our programs to strict mode, we’ve tweaked our recursive functions to be in proper tail call form, and we’ve even seen examples. The final (and as of right now, the most difficult part) is to execute our ES6 code in an environment that can actually handle tail call optimization, and this is where we hit a bit of a snag. The implementation of tail recursion is a feature of the interpreting engine, e.g. V8 in Chrome, where as the availability to execute our newly optimized recursion is dependent upon the compiler rather than the language itself.

The most up-to-date reference of tail call availability (in addition to all other ES6 features) can be found here, and at the time of writing this article there currently isn’t a single browser that has an implementation. This shouldn’t stifle our interest for new language/implementation features however. If we arm ourselves with the knowledge of the soon-to-be toolsets at our disposal, we stand to be all the more prepared to write clean highly optimized code - a characteristic of a great programmers.

This is an exciting feature for a vastly new implementation of JavaScript, and in time we will be tail recursing all over the place. In the mean time, to get a head start on other features of ES6 I recommend traceur and 6to5, both which allow you to write ES6 code and transpile it to valid useable ES5.

Bonus, if you want to see a neat example of recursion in the real-world, Google it.

Additional Reads: Aside from Guillaume Lathoud’s research on tail recursion, I highly recommend checking out Aaron Frost’s JS.Next: ES6 workshop on FrontEndMasters.com. It provides a great introductory overview of the numerous ECMAScript 6 features, and it’s primarily what inspired me to write this article.

Chris Amatangelo is a Web Engineer at DOOR3. Contact us today!