Understanding Tail Recursion

A tail call is the last call executed in a function; if a tail call leads to the parent function being invoked again, then the function is tail recursive.

function bar() {};
function baz() {};
function biz() {};

function foo() {
  bar();
  return baz();
}

function foo2() {
  if(bar()){
    return baz();
  } else {
    return biz();
  }
}

In the first function – foo; the baz() function is a tail call while in foo2, the baz and biz are tail calls because both are the last calls to get executed in the function. The second example shows that the tail call doesn’t have to be the last line of the function – it just has to be the last call the function makes before it returns.

Deep Dive into Stack Overflow

Lets analyze the factorial function.

function fact(n) {
  if(n <= 1) {
    return 1;
  } else {
    return n * fact(n-1);
  }
}

fact(5);
//120

fact(30000);
//RangeError: Maximum call stack
//size exceeded

A fact(3) call is traced out below:

fact(3) -> 3 * fact(2)
3 * (2 * fact(1))
3 * (2 * 1)
3 * 2
6

Every recursive call has to be totally evaluated before the final value can be calculated.

Now let’s make a tail-recursive version of the same function.

function fact2(n) {
    function tailFact(n, acc) {
      if(n <= 1) { return acc; }
      return tailFact(n-1, n * acc);
    }

    return tailFact(n, 1);
}

Evaluation of this function now looks like this:

fact2(3) -> tailFact(3, 1)
tailFact((3-1), (3*1))
tailFact(2, 3)
tailFact((2 -1), (2*3))
tailFact(1, 6)
6

The tail recursive function does not use the stack; the function calculates the factorial as it goes along! The last recursive call performs a simple calculation based on the input arguments and returns.

Thus, there is no need to push frames on to the stack because the new function  already has everything it needs. As such stack overflows would not occur with tail call optimized functions.

One neat little thing to know is that the tail-recursive calls do not change the original values; in the factorial function example above, the value of n is never changed, rather new n values are passed in to new function calls.

Optimizing tail calls

A few languages (e.g. scheme) will optimize tail calls so that they run as loops however other languages e.g. JavaScript, Python do not; even if a function is in the tail call form; it’ll still run out of stack space.

The trick to get a non-optimizing compiler to simulate tail recursion involves the use of a trampoline; lets see examples below

//tail-call version runs out of space

fact2(30000);
//RangeError: Maximum call stack
//size exceeded

function trampoline(fn) {
  var result = fn;
  while (result instanceof Function) {
    result = result();
  }
  return result;
}

// Has subtle error
function fact3(n){
  function tailFact(n, acc){
    if(n <= 1) { return acc;}
    return tailFact(n-1, n*acc);
  }

  return trampoline(tailFact(n,1));
}

fact3(30000);
//RangeError: Maximum call stack
//size exceeded

The fact3 function trampoline call fails because we pass in a function expression and not a function reference. The execution steps are traced out below:

fact3(2)
trampoline(tailFact(2,1))
trampoline(tailFact(1, 2))
trampoline(2);

The trampoline is only called after the tailFact completes its recursive operations. We need to make two changes:

1. Return a function reference from the tailFact function.

2. Pass in a function reference to the trampoline function.

The Function.prototype.bind function is perfectly suited for this purpose and the transformed functions are

//Tail recursive
function fact4(n){
    function tailFact(n, acc){
        if(n <= 1) { return acc;}
        //return function reference
        return tailFact.bind(null,n-1,n*acc);
    }

    //update to function reference
    return trampoline(
        tailFact.bind(null,n,1)
    );
}

fact4(30000);
//Infinity
[/code]

Benefits of tail calls

The biggest advantage of using tail calls is that they allow you to do extensive operations without exceeding the call stack. This makes it possible to do a lot of work in constant space without running into out of memory exceptions; this happens because the frame for the currently executing function is re-used by the newly-executed function call.

It is possible to write the same function using tail call recursion and this will allow you to do it for arbitrarily large values. The space optimization is from O(n) to O(1) since every new function call reuses existing frames rather than pushing stuff on the stack.

Another advantage is that tail calls are essential for the continuation passing style (also called fluent programming; a popular example is jQuery function chains). Imagine chaining a huge set of calls together without needing to worry about running out of stack space – after all you need a location to store the executing functions.

The disadvantage of tail-call optimized code however is that it is difficult to debug; how would you know what function call lead to what function call if the call stack frames are being reused?

Conclusion

Do share your thoughts about tail recursion in the comments or check out these other exciting posts!

1. JavaScript’s Function.prototype.bind

2. Quirky Quirky JavaScript: Episode One

3. The Immediately Invoked Function Expression

4. Functional JavaScript – Tail Call Optimization and Trampolines

Addendum

I spent about a week trying to figure out why my original trampoline didn’t work until I ran into Don Taylor’s excellent article; it sure did help! Can you figure out why it’s wrong too?

function trampoline(fn) {
    var res = fn();
    while (res && res instanceof Function) {
        res = res();
    }
    return res;
}