JS Tail Call Optimisation

The problem

If a function calls itself recursively then the JavaScript engine has to create a new 'stack' (i.e. allocate a chunk of memory) to keep track of the function's arguments.

Let's look at an example of this happening:

function sum(x, y) {
    if (y > 0) {
      return sum(x + 1, y - 1);
    } else {
      return x;
    }
}

sum(1, 10); // => 11

In the above code, the JavaScript engine has to create a new stack for each recursive call.

This happens because the original call to the sum function (i.e. sum(1, 10)) doesn't complete until the very last call to sum returns the value of x. Then x is returned to the caller and that caller returns x to its caller, all the way back to the very first call to sum where by it returns the result of the line return sum(x + 1, y - 1); (which ultimately was the value of x passed along from the last call to sum).

If we create a stack deep enough (e.g. sum(1, 100000)) then the JavaScript engine will throw a RangeError: Maximum call stack size exceeded.

The solution

The fix to this problem is to use fewer stacks.

To achieve this we could rewrite the code to not be recursive; so in other words: use a loop!

The problem with using a loop is that it's not as elegant (or clean/easy to read) as the recursive style of functional programming.

Another solution is to use a type of functional pattern called "trampolining". Let's take a look at one implementation of it...

Example solution

function tco(f) {
    var value;
    var active = false;
    var accumulated = [];

    return function accumulator() {
        accumulated.push(arguments);

        if (!active) {
            active = true;

            while (accumulated.length) {
                value = f.apply(this, accumulated.shift());
            }

            active = false;

            return value;
        }
    }
}

var sum = tco(function(x, y) {
    if (y > 0) {
      return sum(x + 1, y - 1)
    }
    else {
      return x
    }
});

sum(1, 100000) // => 100001

Here we've written a tco function which wraps around the same code we had previously.

Explanation

This could take some time to wrap your head around (lord knows it took me long enough), so if you don't get it the first time around then it's probably best to execute the above code via your browsers developer tools and use a debugger statement to step through the code whilst reading this explanation...

Note: the above code is an abstraction I found here: https://gist.github.com/Gozala/1697037. It makes tail call optimising any function really easy.

We store the result of calling tco (wrapped around our code) into the sum variable.
The sum variable is now a function expression that when called (e.g. sum(1, 10)) will execute the accumulator function that tco returned.
The accumulator is a closure (meaning when we call sum the accumulator will have access to the variables defined inside of tco -> value, active and accumulated; as well as our own code which is accessible via the identifier f).
When we call sum for the first time (e.g. sum(1, 10)) we indirectly execute accumulator.
The first thing we do inside of accumulator is push the arguments object (and Array-like object) into the accumulated Array (so the accumulated will now have a length of 1).
It's worth knowing that the accumulated Array only ever has 1 item inside of it (as we'll soon see).
The active variable by default is false. So as accumulator is called for the first time, we end up inside the if conditional, and then reset active to true.
Now we get to a while loop (we're still calling functions recursively, as you'll see in a moment; but this is a very clean loop compared to an ugly for loop with lots of operators/operands).
The while loop simply checks whether the accumulated Array has any content. If it does then we call the f function and pass through the arguments that were inside accumulated[0] (for the first run of this function that would've been [1, 10]).
When we pass the contents of accumulated[0] we use the shift Array method to actually remove it from the accumulated Array so it now has a length of zero.
If we ignore for a moment the code inside the loop; on the next iteration of this loop the condition of accumulated.length will fail and so we would end up setting active to false and ultimately return to sum the value of the variable value.
This is where it gets confusing, but hold tight!
The f function is our own code. Our own code calls the sum function (which indirectly calls the accumulator function).

The secret sauce to this entire chunk of code is coming up!

If our code returns x then the while loop will stop (I'll explain why in a moment).
If our code can't return x (notice our code has a conditional check to see if y is greater than zero, if it is then we return x, otherwise...) we call sum again and pass through modified arguments.
This time when we call sum we don't get inside of the if conditional because active is already set to true.
So the purpose of calling sum from inside our own code is simply to allow us to store the newly modified arguments inside the accumulated Array.
The sum function then returns undefined (as we weren't able to move into the if conditional)
The flow of control then throws us back into the original while loop (that's still going, it hasn't stopped yet) and undefined is what's stored into the value variable.
At this point the accumulated Array has once again got some content and so the while loop's condition passes once more.
And that is where the recursive magic happens. At some point our code is going to call sum with the y argument set to zero meaning that when the accumulator function calls our code the condition y > 0 will fail and so we return the value of x (which has been incremented each time along the way).
When that happens, x is returned and assigned as the value to the value variable, and so our code never called sum and thus the accumulated Array is never modified again; meaning the while loop condition inside the accumulator function will fail and thus the accumulator function will end returning whatever value is stored inside the value variable (which in this example is the value of x).

Alternative implementations?

There is another implementation I've seen which is much simpler to understand but not necessarily as easy to abstract like the tco method above.

Let's take a look at the code first (note: my explanation assumes an understanding of the this keyword and changing its context, if you're unsure then read more about it here):

function trampoline(f) {
    while (f && f instanceof Function) {
        f = f();
    }
    return f;
}

function sum(x, y) {
    function recur(x, y) {
        if (y > 0) {
          return recur.bind(null, x + 1, y - 1);
        } else {
          return x;
        }
    }

    return trampoline(recur.bind(null, x, y));
}

sum(1, 10); // => 11

It breaks down like this...

We call sum(1, 10).
Our sum function ultimately returns a value. In this case whatever is returned by calling the trampoline function.
The trampoline function accepts a reference to a function as its argument (it's important to understand it needs a reference to a function; doing return trampoline(recur(x, y)) wouldn't work as that would end up just passing the result of calling recur(x, y) to the trampoline function).
So we use Function#bind to pass a reference to the recur function (we use null as the this binding because it doesn't matter what the context the function executes in as we don't use the function as a constructor).
When we execute sum(1, 10) we pass the reference to the internal recur method to the trampoline function.
The trampoline function checks if we passed a function and if so we execute the function and store its return value inside the f variable.
If what we pass into the trampoline function isn't a function then we assume it's the end (i.e. accumulated) value and we just return the value straight back to the sum function which returns that value as the accumulated value.
Inside the recur function we check to see if y is greater than zero, and if it is we modify the x and y values (like we did in the previous example) and then return another reference to the recur function but this time with the modified x and y values.
Inside the trampoline function the newly referenced function is assigned to the f variable and the while loop on its next iteration checks to see if f is indeed a function or not. If it is (which it would be in this instance) we again execute the function (which is now recur(2, 9)) and the whole process starts again.
Until of course we reach the point where y is set to zero. Then when the trampoline function executes the function reference (recur) and inside the if conditional fails (as y is now zero and no longer greater than zero) and so we return the accumulated x value; which then gets sent back and stored in the f variable inside the trampoline function.
On the next iteration of the while loop, f is now a value and not a function and so the while loop ends and the accumulated value is returned to the sum function which returns that as its accumulated value.

The following is copied directly from: http://aphyr.com/tags/Clojure-from-the-ground-up and it provides an alternative explanation of the problem/solution. I've commented the Clojure code heavily for those unfamiliar with it.

Every time you call a function, the arguments for that function are stored in memory, in a region called the stack. They remain there for as long as the function is being called (including any deeper function calls).

Below is a Clojure example (both commented and non-commented version):

; define a multi-arity function (different code branches depending on args provided when called)
(defn sum
  ; arity branch 1
  ; accepts a single argument: numbers
  ([numbers]
   ; the following expression/form is the body of the function
   ; here we re-call the sum function again but provide two arguments (so we will reach the 2nd branch)
   ; this is a defensive way to ensure a function is called correctly
   (sum 0 numbers))
  ; arity branch 2
  ; accepts two arguments: subtotal and numbers
  ; the subtotal argument acts as an 'accumulator'
  ([subtotal numbers]
   ; the following expression/form is the body of the function
   ; we define an if condition (a special kind of conditional that does two things)
   ; if the expression (first numbers) returns something truthy then store that in the n let
   ; so we can use it within the if statement (otherwise the value of n is nil)
   (if-let [n (first numbers)]
     ; if condition is truthy...
     ; recursively call this current function using the recur function
     ; we pass in the result of two sub expressions (+ subtotal n) and (rest numbers)
     (recur (+ subtotal n) (rest numbers))
     ; if condition is falsey...
     subtotal)))

(defn sum
  ([numbers]
   (sum 0 numbers))
  ([subtotal numbers]
   (if-let [n (first numbers)]
     (recur (+ subtotal n) (rest numbers))
     subtotal)))

The result of which is...

user=> (sum (range 100000))
4999950000

We’ve added an additional parameter to the function. In its two-argument form, sum now takes an accumulator, subtotal, which represents the count so far. In addition, recur has taken the place of sum.

Notice, however, that the final expression to be evaluated is not +, but sum (viz recur) itself. We don’t need to hang on to any of the variables in this function any more, because the final return value won’t depend on them.

recur hints to the Clojure compiler that we don’t need to hold on to the stack, and can re-use that space for other things. This is called a tail-recursive function, and it requires only a single stack frame no matter how deep the recursive calls go.

Integralist/1. TCO description.md

The problem

The solution

Example solution

Explanation

Alternative implementations?

jamen commented Jan 23, 2017

glathoud commented Jun 21, 2018