tail_recursive.js

/*
 * Reference:
 * http://wasabiz.hatenablog.com/entry/20110118/1295335821
 * http://code.activestate.com/recipes/496691/
 */

function TailRecursive(func) {
    this.func        = func;
    this.isFirstCall = true;
    this.continueKey = {};
    this.thisArg     = undefined;
    this.args        = undefined;
}

TailRecursive.prototype.apply = function (thisArg, args) {
    if (this.isFirstCall) {
        this.isFirstCall = false;
        try {
            while (true) {
                var result = this.func.apply(thisArg, args);
                if (result === this.continueKey) {
                    thisArg = this.thisArg;
                    args    = this.args;
                }
                else {
                    return result;
                }
            }
        }
        finally {
            this.isFirstCall = true;
        }
    }
    else {
        this.thisArg = thisArg;
        this.args    = args;
        return this.continueKey;
    }
};

function tr(func) {
    var _tr = new TailRecursive(func);
    return function () {
        return _tr.apply(this, arguments);
    };
}

var fact = tr(function (n, acc) {
    return n == 0 ? acc : fact(n - 1, n * acc);
});

console.log(fact(100000, 1)); // -> Infinity

var even = tr(function (n) {
    return n == 0 ? true : odd(n - 1);
});
var odd = tr(function (n) {
    return n == 0 ? false : even(n - 1);
});

console.log(even(100000)); // -> true
console.log(odd(100000));  // -> false

var obj = {};
obj.foo = tr(function (n) {
    return n <= 0 ? this.bar : obj.foo(n - 1);
});
obj.bar = "hoge";
console.log(obj.foo(10)); // -> "hoge"

var nyan = {};
nyan.foo = obj.foo;
nyan.bar = "nyan";
console.log(nyan.foo(0));  // -> "nyan"
console.log(nyan.foo(10)); // -> "hoge"

var fact2 = function (n, acc) {
    return n == 0 ? acc : fact2(n - 1, n * acc);
};

var k;

console.time();
for (k = 0; k < 10000; k++) {
    fact(100, 1);
}
console.timeEnd();

console.time();
for (k = 0; k < 10000; k++) {
    fact2(100, 1);
}
console.timeEnd();