Trampoline & Tail Call Optimization

0-recursion-to-loops-readme.md

The code samples are taken from

• http://www.integralist.co.uk/posts/understanding-recursion-in-functional-javascript-programming/
• https://gist.github.com/Gozala/1697037

1-naive-even-number-finder.js

/*
This is a naive way to find if a number is even
The purpose is to show that recursive calls result in Maximum call stack size exceeded error
*/
function isEven(n) {
    if(n === 1) {
        return false;
    }
    if (n ===2) {
        return true;
    }
    return isEven(n - 2); //recursion
}

var x = 99999; //some large number
console.log(x + ' is even: ' + isEven(x)); 

//Results in the following error:
//Uncaught RangeError: Maximum call stack size exceeded

2-slightly-better-even-number-finder.js

/*
This is slightly better over the previous version 
It wraps recursion call in a function
But it leaves it up to the user to call the function multiple times
This will work for large numbers but is not practical
*/
function isEven(n) {
    if(n === 1) {
        return false;
    }
    if (n ===2) {
        return true;
    }
    //instead of recursively calling this function we wrap it in a function
    return function () {
        return isEven(n - 2); 
    }
}

var x = 9;
console.log(x + ' is even: ' + isEven(x)()()()());

3-trampoline-version1.js

/*
Here we use trampoline function to convert recurion to a loop
This works (even for large numbers) but has two issues
    a. for every function we need to create a corresponding trampoline
    b. Out isEven function looks odd returning a function
*/
function trampoline(f, n) {
    var value = f(n);
    
    while (typeof value === 'function') {
        value = value();
    }
    return value;
}

function isEven(n) {
    if(n === 1) {
        return false;
    }
    if (n ===2) {
        return true;
    }
    //instead of recursively calling this function we wrap it in a function
    return function () {
        return isEven(n - 2); 
    }
}

var x = 99999;
console.log(x + ' is even: ' + tranpoline(isEven, x));

4-trampoline-version2.js

/*
Here we fix the first issue listed in above version
*/
function trampoline(f) {
    var value = f(Array.prototype.slice.call(arguments, 1));
    while (typeof value === 'function') {
        value = value();
    }
    return value;
}

function isEven(n) {
    if(n === 1) {
        return false;
    }
    if (n ===2) {
        return true;
    }
    //instead of recursively calling this function we wrap it in a function
    return function () {
        return isEven(n - 2); 
    }
}

var x = 99999;
console.log(x + ' is even: ' + tranpoline(isEven, x));

5-tail-call-optimization.js

/*
The implementation for tail-call-optimization function is taken from https://gist.github.com/Gozala/1697037
*/
function tco(f) {
    var value, isActive = false, accumulated = [];

    return function accumulator() {
        accumulated.push(arguments);

        if(!isActive) {
            isActive = true;

            while(accumulated.length) {
                value = f.apply(this, accumulated.shift());
            }    

            isActive = false;
        }
            
        return value;
    };
};

var isEven = tco(function (n) {
    if(n === 1) {
        return false;
    }
    if (n ===2) {
        return true;
    }
    return isEven(n - 2);
});

var x = 999999;
console.log(x + ' is even: ' + isEven(x));