If you’ve been on the business for some time, you have, most likely, come across the definition of recursion, for which the factorial of a given number n! = n * (n - 1) * ... * 1 is a standard example.

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

The example shown above is but the most naive implementation of the factorial function.

For the sake of completeness, let’s look at how this executes for n = 6:

  • factorial(6)
    • 6 * factorial(5)
      • 5 * factorial (4)
        • 4 * factorial(3)
          • 3 * factorial(2)
            • 2 * factorial(1)
              • 1 * factorial(0)
                • 1
              • (resuming previous execution) 1 * 1 = 1
            • (resuming…) 2 * 1 = 2
          • (…) 3 * 2 = 6
        • … 4 * 6 = 24
      • 5 * 24 = 120
    • 6 * 120 = 720
  • factorial(6) = 720

Now, we must be very cautious as to what’s happening so we can understand what is to come next.

When we invoke a function, several things happen at once. The location to which we must return to after calling the function is saved, along with the information of the current frame (i.e, the value of n). Then space is allocated for the new function and a new frame is born.

This goes on and on, we keep stacking these frames and then we unwind that stack, replacing function calls with values returned by them.

Another thing to notice is the shape of the process generated by our function. You might not be surprised if I call this shape recursive. We have, thus, a recursive process.

Let’s take a look at a second implementation of this function.

function factorial(n, res) {
    if (n === 0) {
        return res;
    }
    return factorial(n - 1, res * n);
}

We can encapsulate functionality a bit further by defining an inner function.

function factorial(n) {
    function inner_factorial(n, res) {
        if (n === 0) {
            return res;
        }
        return inner_factorial(n - 1, res * n);
    }
    return inner_factorial(n, 1);
}

Let’s take a look at how this gets executed:

  • factorial(6)
    • inner anonymous function (iaf) gets called with (n = 6, res = 1)
      • iaf(5, 1 * 6)
        • iaf(4, 6 * 5)
          • iaf(3, 30 * 4)
            • iaf(2, 120 * 3)
              • iaf(1, 360 * 2)
                • iaf(0, 720)
                  • 720
                • 720
              • 720
            • 720
          • 720
        • 720
      • 720
    • iaf (6, 1) = 720
  • factorial(6) = 720

You might notice that we didn’t need to perform any calculation after unwinding the stack. We just returned a value. But, according to our rules, we had to save the state as a stack frame, even if it weren’t of any use later in the chain.

Our rules, however, are not applied to every language out there. In fact, in Scheme it’s mandatory for such chains to be optimized with tail call optimization. This ensures that our stack is not filled with unnecessary frames. Our previous calculation would look, thus, this way:

  • factorial(6)
  • iaf(6, 1)
  • iaf(5, 6)
  • iaf(4, 30)
  • iaf(3, 120)
  • iaf(2, 360)
  • iaf(1, 720)
  • iaf(0, 720)
  • 720

Which in turns, looks an awfully lot like

res = 1;
n = 6;

while(n > 1) {
    res = res * n;
    n--;
}

This means, we actually have an iterative process, even if we’re using recursion. How cool is that?

The good news is, this is a feature in ES6. As long as your recursive call is in tail position and your function has strict mode, tail call optimization will kick in and save you from having a maximum stack size exceeded error.

UPDATE Dec 1, 2017: The only major browser with tail call optimization is Safari.1 V8 has an implentation2 but has not shipped it yet3 for the reasons listed.

1: https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation)

2: https://bugs.chromium.org/p/v8/issues/detail?id=4698

3: https://v8project.blogspot.com/2016/04/es6-es7-and-beyond.html

>_ Improve this tip