Skip to content

Instantly share code, notes, and snippets.

@yoavrubin
Created December 12, 2013 20:56

Revisions

  1. yoavrubin created this gist Dec 12, 2013.
    96 changes: 96 additions & 0 deletions factorial.js
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,96 @@

    // the most basic factorial
    function fact1(n){
    if(n < 2) return 1;
    return n*fact1(n-1);
    }

    // let's add some precondition verifications
    function fact2(n){
    if(typeof n !== 'number' || isNaN(n) || n < 0)
    return -1;
    if(n<2) return 1;
    return n*fact2(n-1);
    }

    // no need to make the verification on each recursive call, let's place the logic in an inner function
    function fact3(){
    if(typeof n !== 'number' || isNaN(n) || n < 0)
    return -1;
    var innerFactorial1 = function(n){
    if(n<2) return 1;
    return n*innerFactorial1(n-1);
    };
    return innerFactorial1(n);
    }


    // let's place the recursive call in a tail position, and hope that ES6 will bring with it tail call optimization
    function fact4(n){
    if(typeof n !== 'number' || isNaN(n) || n < 0)
    return -1;
    var innerFactorial2 = function(n, accum){
    if(n<2) return accum;
    return innerFactorial2(n-1, n*accum);
    };
    return innerFactorial2(n,1);
    }

    // well, we don't actually have to wait for ES6 to bring the tail call optimization, we can use trampoline
    function fact5(n){
    if(typeof n !== 'number' || isNaN(n) || n < 0)
    return -1;
    var trampoline = function (func){
    var res = func;
    while(typeof res === "function")
    res = res();
    return res;
    };
    var innerFactorial3 = function (n, accum){
    if(n < 2){
    return accum;
    }
    return function(){
    return innerFactorial3(n-1, accum*n);
    };
    };

    return trampoline(
    function(){
    return innerFactorial3(n,1);
    }
    );
    }

    // Now let's cache the results within the function so we can use it in an identical future call, and we have our
    // final version of factorial

    function fact6(n){
    if(typeof n !== 'number' || isNaN(n) || n < 0)
    return -1;
    fact6._cache = fact6._cache || [];
    if(fact6._cache[n])
    return fact6._cache[n];
    var trampoline = function (func){
    var res = func;
    while(typeof res === "function")
    res = res();
    return res;
    };
    var innerFactorial4 = function (n, accum){
    if(n < 2){
    return accum;
    }
    return function(){
    return innerFactorial4(n-1, accum*n);
    };
    };

    var result = trampoline(
    function(){
    return innerFactorial4(n,1);
    }
    );
    fact6._cache[n] = result;
    return result;
    }