Do you even recurse?... And if you do, do you do it safely?

Background

Have you ever written a factorial function? If you have then you might have done something like:

function factorial(n) {
  let result = n;

  for (let i = n - 1; i > 1; i++) {
    result = result * i;
  }

  return result;
}

Or even something like:

function factorial(n) {
  return a > 1 
    ? n * factorial(n - 1) 
    : 1;
}

Both are valid approaches but there is something about the second approach that makes it easier to understand what it is doing, we can easily read what factorial does is n * (n - 1)! and that it calls itself until n equals 1 and then we finish, that is what we call a recursive function:

A function that either calls itself or is in a potential cycle of function calls.

The problem

Recursion is great, it helps us write more concise, readable and simple code. However, there is a big drawback regarding recursion, take for instance our factorial function, when we call factorial(5) we get 120, however, if we call the same function with a way bigger value, let's say 12,000 we get a whole different result:

RangeError: Maximum call stack size exceeded

You see, every runtime has a maximum stack size (node has a limit of around 11k), so when we make long recursive cycles our program crashes as there is no more stack space.

The solution

Fortunately, there is an alternative that allows us to safely write recursive functions, Tail Call Optimization.

TCO is a process that many languages have implemented to deal with long recursive chains. It is based on the premise that when a procedure/function calls a subroutine as its final action, then it is possible to replace the current call stack frame with the frame of the new invocation, hence, being as performant as the looped version of that function.

So, how would we modify our factorial function to fulfill this constraint? We could do the following:

function factorial(n, acc = 1) {
  return n > 1 
    ? factorial(n - 1, n * acc) 
    : acc;
}

As you see we added a property, acc, which allows us to pass down any relevant information (our current accumulative product) to the next factorial invocation, thus, rendering all the information of the previous call useless and allowing us to get rid of that stack frame, so, instead of having 11k+ stack frames, we would be replacing the same frame 11k+ times.

Pretty neat right?

Sadly, even though TCO is part of the javascript specification, many engines have decided not to implement it.

An interesting alternative

Despite this, there is still a safe way to use recursion. We can implement our own version of TCO.

According to what we have seen of TCO our aim should be to make a way for recursive functions to behave in a way that instead of having a linear growth of the stack size we keep a constant size, so let's ask ourselves, what control-flow structure do we know that behaves that way? Loops! So what if we had a loop that executed functions repetitively? Well, that is what we call a trampoline.

A trampoline is a special kind of loop that executes thunked-functions, that is, functions that return the next function to call. So, what if we converted each of our recursive calls into a thunk, and pass it to a trampoline? Would our stack maintain a constant size? Let's see:

First, we've got to rewrite our factorial function to be a thunked-function, which would be something like:

function factorial(n, ret = res => res) {
  return n > 1 
    ? () => factorial(n - 1, res => ret(n * res)) 
    : ret(1);
}

Let's analyze what we did there, shall we?

1. We added an argument to the function signature, ret, which as you see is a function, that fulfills a special role, it allows us to compose our thunks.
2. We now return a function instead of the value of the factorial computation, by doing that we intend to defer the execution of that function until our trampoline decides to call it.

So let's get into our trampoline implementation.

As we said a trampoline is a loop that executes thunked-functions one at a time, so, taking advantage of the decorator pattern we could write the following:

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);

    while (result && typeof result === 'function') {
      result = result();
    }

    return result;
  };
}

As you realize the implementation is rather simple, we decorate our recursive function with our trampoline in order to do TCO. There are somethings worth noticing here:

1. The while runs until there are no more functions to call.
2. Our fn parameter is only used at the beginning since each result represents the next function to call.

So our final result would be something like:

As you can see our call stack never steps pass the 13 frames, which allows us to work with longer recursive chains without worrying about a stack overflow.

A little extra

Even though the trampoline function works nicely I would still add something else to our API, a Symbol! yeah, one of those new things with ES6 that allow us to do metaprogramming, so my final implementation would be:

function factorial(n, ret = res => res) {
  return n > 1
    ? {
        fn: () => factorial(n - 1, res => ret(n * res)),
        [Symbol.for('recurse')]: true
      }
    : ret(1);
}

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);

    while (result && result[Symbol.for('recurse')]) {
      result = result.fn();
    }

    return result;
  };
}

// Or with Decorator syntax


@trampoline
function factorial(n, ret = res => res) {
  // ...
}

That way we can be sure that we stop when we are supposed to, not after.

Finale

Recursion is great, one of the pillars of functional declarative programming, however, it has an interesting drawback, which can cause some unintended issues. Here we saw how to optimize a recursive call using tail calls. It is also important to note that by making the execution path more complex the performance (time-wise) decreases, so use this method with consideration and avoid adding extra layers of complexity where is not needed.

I hope you find this article useful, please let me know what you think about this implementation of TCO.

p.s. While doing research in this topic I stumbled with this awesome article which mentions the possibility of accomplishing a similar effect using python generators, so I'll be researching a way to use ES6 generators to improve the way we are optimizing our recursive calls.