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

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

Benefits

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;
}
Advertisements

16 thoughts on “Understanding Tail Recursion

  1. Tail recursion incorrect, it increases call stack by 1 in all languages. Double checked and confirmed in Ecma 5, and C#.
    “As such stack overflows would not occur with tail call optimized functions.” then later “even if a function is in the tail call form; it’ll still run out of stack space.”.

    Like

    • Hi Andy,

      Thanks for the feedback.

      The tail recursive call is a function call like any other so it gets put on the stack. However unlike typical recursive calls, it does not add extra frames on the stack. A pure recursive function will continue to add stack frames until it reaches the base case.

      The second quote was regarding languages that do not support tail-call optimization; JS currently does not and as such even if you write your recursive functions in a way that a tail-call optimized compiler can execute it in an iterative way; languages without support for this will still execute it as a pure recursive function and run out of stack space.

      I hope this explains it clearly.

      Like

    • Very much wrong. A compiler that implements optimization for tail recursion, say, GCC, will modify the tail recursive function so that instead of executing another function call and increasing the stack for each call, it’ll simply modify the function parameters and execute again from the beginning.

      Liked by 1 person

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

    res = fn() will return a value.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s