I’ve always heard about optimizing recursions with tail call optimization (TCO), so lately I’ve decided to learn more about it. While it seemed pretty cool that we can bring the performance of a recursive loop closer to that of the manual loop, I was in for a big disappointment.

Even tough TCO was supposed to be supported in Javascript since ES6 came out, modern browsers have yet to support it, Hence this article is meant to expand your knowledge instead of being actionable advice.

Note: I’ve read that currently, only Safari with strict mode supports TCO. I don’t own a Mac to check against the latest Safari version so I’ve tried testing it with Safari for Windows 5.1.7, which is the last available release for windows, but with no success. The call stack still increases, but maybe newer versions are up for the task.

ES6 introduced a compiler enhancement that flattens the execution of recursive calls into a single call stack frame, but this can only occur when the last act of the recursive call is to call another function, this last act is said to be in a tail position, hence the name.

The most famous error message when dealing with a recursive call is Range Error: Maximum call stack size exceeded

!(range error maximum call stack size exceeded)[./range-error-maximum-call-stack-size-exceeded.png]

When you call a function, a new function context is created and the call stack increases, when you keep calling functions inside functions the call stack keeps increasing until it reaches a maximum stack size.

When using tail call optimization the Javascript runtime realizes it doesn’t need to hold on to the current stack frame because it does not have anything more to do. This way each recursive call happens in a new stack frame every time. Therefore you will never reach the maximum call stack size.

In simple terms, you can call a function from another function without growing your call stack ( With TCO ).

The following code will call three functions: funcA, funcB & funcC. Each time we call a function from inside another function we increase the call stack.

function funcA() {
  console.log("A");
  funcB();
}

function funcB() {
  console.log("B");
  funcC();
}

function funcC() {
  console.log("C");
}

funcA();
// Prints to the console:
// A
// B
// C

Let’s look at the call stack of the above code:

You can see that each function call increases the stack size until it reaches the deepest function call ( funcC ), then it will unwind those frames from the stack.

Course by Sagi Liba,
Author of this blog

Transforming a Recursion to a Tail position

Let’s start with a simple recursion that sums all the numbers until a given number:

function sumRecursion(num) {
  if (num === 0) {
    return 0;
  }
  return num + sumRecursion(num - 1);
}

sumRecursion(10); // returns 55

To transform our recursion into a tail position we have to:

• Make sure the last act of the recursive call is to call another function.

• Any state that needs to be saved will be passed as arguments to the function call.

function sumRecursionTCO(num, accumulator = 0) {
  if (num === 0) {
    return accumulator;
  }
  return sumRecursionTCO(num - 1, accumulator + num);
}

Let’s make sure we moved the recursion into a tail position.

It seems that we have followed the rules, and the recursion is indeed in a tail position.

Why did we need an accumulator argument?

In our regular recursion, the final act of the function is to create an addition operation with the next recursive call, when all the recursive functions have been evaluated it will sum up all of the results and return our value.

In a tail call optimized recursion we have to keep our results somewhere, so we use the accumulator argument to keep our addition results until it returns the final calculation.

As you can see I’ve also set a default value for the accumulator so we don’t have to set a starting value for it manually.

Now will take it up a notch by moving a Fibonacci recursion into a tail position:

function fibonacci(num) {
  if (num <= 1) return 1;

  return fibonacci(num - 1) + fibonacci(num - 2);
}

This recursion will increase the size of the call stack because the inner function calls needs to be evaluated before the addition operation can be calculated.

Here is a tree visualization of all the calls that will be made when calling the function with the value of 5:

Now to move the recursion into a tail position we must remember the rules:

• Make sure the last act of the recursive call is to call another function.

• Any state that needs to be saved will be passed as arguments to the function call.

function fibonacci(num, a = 1, b = 1) {
  if (num <= 2) return a;
  return fibonacci(num - 1, a + b, a);
}

As you can see the last act of the function is to call fibonacci recursively, and I’ve moved the state, the data that needs to persist between calls as arguments.

Again I’ve used default values to initialize the function arguments to make sure it works without passing them manually.

Now the call stack will evaluate each recursive function call in a new stack frame and discard the previous frame, that is because the Javascript run time will detect that the function is in a tail position.

A final note about moving a recursion into a tail position. Remember that the last act of the function is to call another function, your last act must not be an operation of any kind, by leaving an operation you will keep growing your call stack because the operation must finish evaluating instead of going into the next function directly and discarding the previous stack frame.

// Operation examples that are not
// in a tail position:

function sumRecursion(num) {
  if (num === 0) {
    return 0;
  }
  // Here we have an operation waiting to be evaluated.
  return num + sumRecursion(num - 1);
}

function fibonacci(num) {
  if (num <= 1) return 1;
  // Another example of an operation waiting to be evaluated.
  return fibonacci(num - 1) + fibonacci(num - 2);
}

Time Complexity

Tail call optimization reduces the time complexity from O(n) to O(1), which is a huge performance boost.

Regular recursion requires a lot of memory because the call stack keeps growing.

Recursion with TCO requires constant memory because it can only make a recursive call or return a value, therefore it does not make any computation that causes the stack frame to be saved in memory, and it discards it instead.

I try my best to write content that will help you in your day to day and will make you a better developer.

This subject, even though it won’t help you right now in your own Javascript projects, it is meant to expand your knowledge further as a developer, and might even help when working with other languages that already support tail calls.

I hope you enjoyed the article.