Trampolining your way out of overflows

You implement a heroically recursive JS function, destined to call “Batman!!” till he
shows up …

var repeat = function (str, n) {
    if (n === 0) { return ''; }

    return str + repeat(str, n - 1);
};

It all goes well, until the recursion depth causes your stack to overflow.

try {
    console.log(repeat("Batman!!", 200000));
} catch (e) {
    console.log(e.message);
}

Since all the right stuff is missing,
you consider replacing recursion with iteration.
But maybe your brain is twisted and the result feels wrong, or difficult to reason about.
You are a unique person, wired for reading recursion, and programs must be written for people to read, and only incidentally for machines to execute.

Worlds colliding

So, what would Batman do? There is a well known method from the LISP world we can use to fake recursion.
It’s main ingredient is a trampoline, a function that will iteratively call another function until a desired result is produced.
Here is a simple implementation assuming that an acceptable result is anything but a function.

(function () {

    var str = Object.prototype.toString,
        isFunction = function (v) {
            return (v && str.call(v) === '[object Function]');
        },
        trampoline;


    trampoline = function (functionCall) {
        var result = functionCall;

        while (isFunction(result)) {
            result = result();
        }

        return result;
    };

})();

With our trusty sidekick ready, we turn our attention to refactoring recursion to trampolining.

Reimagining the recursion

Let’s split the recursive function into

  • A repeating function, that evaluates to either the result or a resuming function.
    It takes any arguments necessary plus a state-keeping argument (in our case, context).

  • A resuming function, that accepts no parameters. It’s sole purpose is
    to resume the repeating function with the correct arguments and state.

The recursive function then, would transform from this

var repeat = function (str, n) {
    if (n === 0) { return ''; }

    return str + repeat(str, n - 1);
};

into this

var repeat = function (str, n, context) {
    if (!context) { context = ''; }

    if (n === 0) {
        return context;
    }

    return function () { return repeat(str, n - 1, context + str); };
};

And would run like so

console.log(trampoline(repeat("Batman!!", 200000)));

So ther you have it. Trampoline-approved functions will not overflow the stack since there is no recursion. Nonetheless,
we still have to make sure that we can meet the stopping condition otherwise it will just turn into an infinite loop.

This thunk-returning function style has more things to offer. It can form the basis of streams and lazy evaluation, but this is a completely different blog post.

Published by pgk

Person

%d bloggers like this: