Memoization in JavaScript

There are many places where you can take advantage of memoization to save computation space and time. One example is computing the n-th term of a fibonacci sequence. Below we are saving or "memoizing" every computed value and ask if we have computed already. If we have, the we will just use that value, otherwise we will calculate it the new value and save it in our object.

var fibo = (function () {  
  var memo = {};
  function fi(n) {
    if (n < 0) { return -1 } else {
      var value = (n in memo) ? memo[n] : (!n || n === 1) ? 1 : fi(n - 1) + fi(n - 2);
      memo[n] = value;
      return value;
    }
  }
  return fi;
})();
view raw  

Basically we are "caching" the previously calculated values so we don't end up repeating the same stack call. Implement this recursively with a large value of n and see what happens:

function fibo (n) {  
  return (!n || n === 1) ? 1 : fibo(n-1) + fibo(n-1);
}

The call stack will grow like a tree, not good ...

alt