« Back to Index

Recursion and Trampolines in JavaScript (code copied from JS Drip Newsletter

View original Gist on GitHub

Tags: #65)

1. TCO Broken Example.js

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

2. Start to flatten.js

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.
 */

3. Working Example.js

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