Tail recursion

JavaScript's routine for handling recursion is known as tail recursion, a stack-based implementation of recursion. This means that, for every recursive call, there is a new frame in the stack.

To illustrate the problems that can arise from this method, let's use the classic recursive algorithm for factorials.

var factorial = function(n) {   if (n == 0) {     // base case     return 1;   }   else {     // recursive case     return n * factorial(n-1);   } }

The algorithm will call itself n times to get the answer. It's literally computing (1 x 1 x 2 x 3 x … x N). That means the time complexity is O(n).

Note

O(n), pronounced "big oh to the n," means that the complexity of the algorithm will grow at a rate of n as the size of the input grows, which is leaner growth. O(n2) is exponential growth, O(log(n)) is logarithmic growth, and so on. This notation can be used for time complexity as well as space complexity.

But, because a new frame in the memory stack is allocated for each iteration, the space complexity is also O(n). This is a problem. This means that memory will be consumed at such a rate the memory limit will be exceeded far too easily. On my laptop, factorial(23456) returns Uncaught Error: RangeError: Maximum call stack size exceeded.

While calculating the factorial of 23,456 is a frivolous endeavor, you can be assured that many problems that are solved with recursion will grow to that size without too much trouble. Consider the case of data trees. The tree could be anything: search applications, file systems, routing tables, and so on. Below is a very simple implementation of the tree traversal function:

var traverse = function(node) {   node.doSomething(); // whatever work needs to be done   node.childern.forEach(traverse); // many recursive calls }

With just two children per node, both time complexity and space complexity, (in the worst case, where the entire tree must be traversed to find the answer), would be O(n2) because there would be two recursive calls each. With many children per node, the complexity would be O(nm) where m is the number of children. And recursion is the preferred algorithm for tree traversal; a while loop would be much more complex and would require the maintenance of a stack.

Exponential growth like this would mean that it would not take a very large tree to throw a RangeError exception. There must be a better way.

The Tail-call elimination

We need a way to eliminate the allocation of new stack frames for every recursive call. This is known as tail-call elimination.

With tail-call elimination, when a function returns the result of calling itself, the language doesn't actually perform another function call. It turns the whole thing into a loop for you.

OK, so how do we do this? With lazy evaluation. If we could rewrite it to fold over a lazy sequence, such that the function returns a value or it returns the result of calling another function without doing anything with that result, then new stack frames don't need to be allocated.

To put it in "tail recursion form", the factorial function would have to be rewritten such that the inner procedure fact calls itself last in the control flow, as shown in the following code snippet:

var factorial = function(n) {   var _fact = function(x, n) {     if (n == 0) {       // base case       return x;     }     else {       // recursive case       return _fact(n*x, n-1);     }   }   return fact(1, n); }

Note

Instead of having the result produced by the first function in the recursion tail (like in n * factorial(n-1)), the result is computed going down the recursion tail (with the call to _fact(r*n, n-1)) and is produced by the last function in this tail (with return r;). The computation goes only one way down, not on its way up. It's relatively easy to process it as an iteration for the interpreter.

However, tail-call elimination does not work in JavaScript. Put the above code into your favorite JavaScript engine and factorial(24567) still returns Uncaught Error: RangeError: Maximum call stack size exceeded exception. Tail-call elimination is listed as a new feature to be included in the next release of ECMAScript, but it will be some time before all browsers implement it.

JavaScript cannot optimize functions that are put into tail recursion form. It's a feature of the language specification and runtime interpreter, plain and simple. It has to do with how the interpreter acquires resources for stack frames. Some languages will reuse the same stack frame when it doesn't need to remember anything new, like in the preceding function. This is how tail-call elimination reduces both time and space complexity.

Unfortunately, JavaScript does not do this. But if it did, it would reorganize the stack frames from this:

call factorial (3)   call fact (3 1)     call fact (2 3)       call fact (1 6)         call fact (0 6)         return 6       return 6     return 6   return 6 return 6

into the following:

call factorial (3)   call fact (3 1)   call fact (2 3)   call fact (1 6)   call fact (0 6)   return 6 return 6