Software Engineer · Teacher · Author · Vegan

Learning Recursion in JavaScript Part 5 - A Factorial Function with Tail Recursion

Last reviewed on May 9, 2020

Ah, recursion, one of those intimidating programming topics that make many developers’ heads spin 🤯 . These types of problems can be difficult to conceptualize, especially when you’re under pressure during an interview. I know I’ve felt that before! Well, that’s why I am writing this blog post series on recursion, to help you and me learn it better. As I’ve spent more time learning about it, I’ve come to find it a fascinating topic and appreciate how elegantly you can use it to solve certain types of problems.

Here are the other posts in this series if you haven’t checked those out yet:

  1. The Obligatory Factorial Function
  2. Sum an Array of Numbers 3 Ways
  3. Flattening Arrays
  4. Palindromes
  5. Revisiting the Factorial Function with Tail Recursion

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.

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:

Disclaimer: Any viewpoints and opinions expressed in this article are those of David Tang and do not reflect those of my employer or any of my colleagues.