Memoization in javascript

In computing, memoization is an optimization technique used primarily to speed up computer programs by keeping the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing in a general top-down parsing algorithm that accommodates ambiguity and left recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling; see also lookup table.

Today I want to explain how memoization can optimize implementing algorithms in javascript.
Let’s suppose we want t write a recursive function to compute Fibonacci numbers. (A Fibonacci number is the sum of the two previous Fibonacci numbers.)

 var computeFibonacci = function (n) {
     return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
 };

If we use the function to compute fubonacci number 0 to 10, the functions would called 435 times. Although we call this 11 times but it calls itself 442 times recursively.

Now, lets see how can we optimize our solution If we memoize the function.
We just try to avoid repetitive computing by saving results in an array and check the array before each call. If we want to compute fibonacci for a number that we already computed, we can immediately find it in the array.

var optimizedFibonacci = function () {
var memo = [0, 1];
var fib = function (n) {
         var result = memo[n];
         if (typeof result !== 'number') {
result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    };
return fib; }( );

This time the function returns the same result, but it is called only 29 times and used memo array to retrieve already computed results.

 
43
Kudos
 
43
Kudos