alexyz

// simple Fibonacci w/o Memoization

var fibonacci = function(n){
     return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
var showF = function(n){
     for(var i = 0; i <= n; i += 1) {
          document.writeln('//' + i + ': ' + fibonacci(i));
     }
};

showF(10); //55

 

//Fibonacci with Memoization

var fibonacci = (function() {
     var memo = {};

     function f(n) {
          var value;
          if (n in memo) {
               value = memo[n];
          } else {
               if (n === 0 || n === 1)
               value = n;
          } else {
               value = f(n - 1) + f(n - 2);
               memo[n] = value;
          }
          return value;
     }
     return f;
})();

document.writeln(fibonacci(50));

 

// Fibonacci with Memoizer abstracted function

var memoizer = function (memo, formula) {
     var recur = function(n) {
          var result = memo[n];
          if(typeof result !== 'number') {
               result = formula(recur, n);
               memo[n] = result;
          }
     return result;
     };
     return recur;
};

var fibonacci2 = memoizer([0,1], function (recur, n) {
     return recur(n - 1) + recur(n - 2);
});

document.writeln(fibonacci2(50)); <span style="color: #ff0000;">//12586269025</span>

 

credit: Crockford, Douglas. JavaScript: The Good Parts, p.45. O’Reilly 2008

credit: http://www.sitepoint.com/implementing-memoization-in-javascript/

This entry was posted on Sunday, July 6th, 2014 at 9:51 pm and is filed under Algorithms, Interview Questions, JavaScript. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.