Improve Your Recursions Performance With Tail Call Optimization

by | Sep 19, 2020 | 0 comments

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

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:

call-stack

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.

Transforming a recursion to A tail call 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.

The last act of the recursion is to call another function √

Our summing value (accumulator) has been passed in the function arguments √

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:

Fibonacci recursion

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.

fibonacci tail call

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.

recursion and tco call stack usage

*     *     * 

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, you can help the blog grow by liking it below.

IF YOU GOT ANY VALUE SHARE 😄