Understanding recursion in functional JavaScript programming

What we'll cover

reading time: approx. 13mins

Introduction

This post isn't about Functional Programming per se, as there are many parts to pure FP (seen in Lisp, Clojure, Haskell etc) which we can't achieve completely in the JavaScript language (for example, implementing fundamental principles of FP such as "immutable data" is very difficult in a language designed around allowing data structures to be mutable. Although immutable data would be a lot easier with ES5 getters/setters and ES6 proxies).

What we do cover is recursion and a problem known as "tail call optimisation" and how to work around it in JavaScript.

The problem

In JavaScript, if a function calls itself recursively then the JavaScript engine has to create what's called a new 'stack'. A stack is a chunk of memory allocated to help keep track of all the information related to the function at the point of execution (such as its arguments and their initialised values).

Here in lies the problem: creating stacks is expensive, as the JavaScript engine can only create as many stacks as it has memory available. If we write a function that recursively calls itself many times then we'll find that we can exhaust the memory allocation and trigger an error.

Let's look at some code that demonstrates this.

The following function sum simply adds two numbers together; but for the purpose of demonstrating recursion (a potentially complex topic) and making it easier to understand, we have written the sum function in a very convoluted way:

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

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

Let's quickly explain what the code does:

As we can see, in the above code the JavaScript engine has to create a new stack for each recursive call. For a small sum of 1 and 10 this is fine; but if we try to sum 1 and 100000 then that'll require more stacks than we have memory to allocate. This will cause an error like so:

sum(1, 100000);
// => `RangeError: Maximum call stack size exceeded`

Recursion in the form we've written it above requires many stacks to be created because of how the function is calling itself.

The first 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 (i.e. sum(0, 99999)). When the final call to sum occurs and we discover that y is no longer greater than x we return the accumulated value which has for each recursive call been stored inside the argument x. That returned value needs to then be passed back through each function execution context (effectively closing each stack) until we reach the very first function execution context that was opened when we ran sum(1, 10).

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

This problem can occur very easily (as we've seen in this simple code example).

Tail Call Optimisation

In other programming languages the recursion could be rewritten in such a way that the engine would recognise a recursive execution was happening and optimise the code internally into a loop form. This is called a "tail call optimisation" (TCO).

Unfortunately the JavaScript language doesn't implement this optimisation.

Note: apparently ECMAScript 6 has plans to implement TCO

The following is an example of a tail optimised version of the previous code...

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

    return recur(x, y);
}

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

This works because the recur function ends up being the last invocation of the sum function. Now the engine is able to construct internal code that executes recur inside of a loop instead of via recursion.

As mentioned above, this optimisation has no effect in the current version of the JavaScript language (fingers crossed ES6 will implement TCO so the above code would work fine).

For now, we need an alternative solution.

The solution

The fix to this problem (in JavaScript at least) is to consume fewer stacks.

One way we could do this is to rewrite the code to not be recursive; so in other words: use a loop! Effectively we would be producing our own implementation of TCO (remember that TCO recognises a recursion and internally implements it as a loop).

The problem with using a loop is that it's not as elegant as the recursive style we associate with functional programming.

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

Replace Recursion with a Loop

Note: the following code (and my explanation of it) assumes an understanding of the this keyword and changing its context. If you're unsure about what this means 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

The reason the above code works is because we've replaced our functional recursion style with a loop.

In the above code we don't create a deep nest of stacks because the sum function only gets called once. The trampoline function also is only called once; and the recur function inside of sum, although called multiple times, is called via a loop (again, no more than one stack is required at any one time).

The code breaks down like so...

A more advanced solution

The previous code we just looked at works fine, but it required us to modify our code to work with the 'trampoline' pattern. This is a bit of a pain and means if we have lots of recursive code then it means each one might need subtle changes to accommodate this pattern.

The following code is an abstraction around that concept and it'll allow us to keep our code exactly the same, with no modifications, and the abstraction will handle all of the work for us!

Let's take a look at the implementation...

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 simply wraps around our original code (so no modification required to our code).

Let's now take a look at how it works.

Explanation

Be warned that understanding this code could take a while (lord knows it took me long enough to figure it out; that's what prompted me to write this post, so I wouldn't forget!).

If you don't understand how the code works after the first time reading through these notes then it's probably best to execute the above code via your browser of choice's developer tools and use a debugger statement to step through the code whilst reading this explanation...

Note: the above code was written by Irakli Gozalishvili (an engineer at Mozilla): https://gist.github.com/Gozala/1697037. As you can see above, it makes tail call optimising any function really easy.

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

Conclusion

There you have it, a quick run through of TCO, what it means and how potentially to work around it in JavaScript. Go forth and be productive!

Update 1

I've since discovered a nice explanation of trampolining in the JS Drip Newsletter (#65).

The following code is an example that is NOT tail-call optimised:

function isEvenNaive (num) {
    if (num === 0) {
        return true;
    }

    if (num === 1) {
        return false;
    }

    return isEvenNaive(Math.abs(num) - 2);
}

isEvenNaive(10);
// => true

isEvenNaive(9);
// => false

isEvenNaive(99999);
// => InternalError: too much recursion

The following code snippet demonstrates the first step towards trampolining, which is to flatten the stack by requiring the user to manually execute the function over and over:

function isEvenInner (num) {
    if (num === 0) {
        return true;
    }

    if (num === 1) {
        return false;
    }

    return function() {
        return isEvenInner(Math.abs(num) - 2);
    };
}

isEvenInner(8);
// => function() {
//        return isEvenInner(Math.abs(num) - 2);
//    };

isEvenInner(8)()()()();
// => true

The first thing to notice about our isEvenInner function is that instead of directly calling itself again, it returns an anonymous function. That means each call to isEvenInner gets resolved immediately, and doesn't increase the size of the stack. It also means that we need a way to automatically invoke all of those anonymous functions that will get returned along the way. That's where trampoline comes in.

The trampoline function effectively turns this recursive algorithm into something that is executed by a while loop. As long as isEvenInner keeps returning functions, trampoline will keep executing them. When we finally reach a non-function value, trampoline will return the result.

Now, finally, let's see an example that automates the execution of the flatterned stack:

function trampoline (func, arg) {
    var value = func(arg);

    while(typeof value === "function") {
        value = value();
    }

    return value;
}

trampoline(isEvenInner, 99999);
// => false

trampoline(isEvenInner, 99998);
// => true

var isEven = trampoline.bind(null, isEvenInner);

isEven(99999);
// => false
Comments

Testing Your Ruby Code With Guard, RSpec & Pry (Part 2)

Another new article published on NetTuts

Learn the basics of test-driven development in Ruby along with many common web development tools such as Guard, RSpec, and Pry, among others (it's part 2 of 2).

You can read it in full on NetTuts here: http://code.tutsplus.com/tutorials/testing-your-ruby-code-with-guard-rspec-pry-part-2--cms-20290

Comments