In the first post, The Obligatory Factorial Function, we looked at writing a factorial(n) function implemented with recursion. In this post, I wanted to show what that same recursive function would look like if it used tail recursion.

What is a Tail Call?

A tail call is a function call that occurs at the end of another function. In the following code, the bar() call is a tail call:

function foo() {
  return bar();
}

What is Tail Recursion?

Tail recursion occurs when the tail call is recursive. For example, the foo() call is a tail call that is recursive:

function foo() {
  return foo();
}

factorial(n) Without Tail Recursion

To refresh ourselves, here is the implementation of the factorial function from The Obligatory Factorial Function without tail recursion:

function factorial(n) {
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

This function does not have tail recursion because the last line is n * factorial(n - 1) as opposed to factorial(...).

factorial(n) With Tail Recursion

Here is the implementation with tail recursion:

function factorial(n, total = 1) {
  if (n === 0) {
    return total;
  }

  return factorial(n - 1, n * total);
}

Why does Tail Recursion matter?

When a recursive function uses tail recursion, it can be optimized by the JavaScript engine. This optimization is called Tail Call Optimization (TCO). The reason I say can is because Tail Call Optimization is part of the JavaScript language specification but it isn't supported by very many browsers at the time of this writing.

Every time we call a function, a stack frame is created, which is a frame of data that stores information about that function call. This stack frame gets pushed onto the call stack, which is a stack data structure that stores all active function invocations.

When a recursive function has Tail Call Optimization, the call stack won't continue to grow. To see this in action, visit the following two JSBin links in Safari with the Console open. Make sure your version of Safari is version 13 or higher.

• factorial(n) with TCO
• factorial(n) without TCO

Click on "Run" in the upper right corner and compare the stack traces in each. Notice how in the example without TCO, the stack frames continue to grow? The call stack has a size limitation which depends on the JavaScript engine. If the call stack exceeds that size, then we get the error: RangeError: Maximum call stack size exceeded. The example with TCO ends up using less memory because the call stack doesn't continue to grow on each recursive call.

If you'd like to learn more about the details of TCO, check out these two posts that I found useful:

• How to use Tail Call Optimizations in JavaScript
• Tail call optimization in ECMAScript 6