Memoization

Introduction

One of the common ways of increasing the efficiency of an algorithm is using the hash, map or dictionary data structure which is a key/value pair data structure. This technique is used to improve the efficiency of recursive algorithms which is called Memoization in dynamic programming.

what is Memoization ?

Memoization is a technique for improving the performance of recursive algorithms. It involves rewriting the recursive algorithm so that as answers to problems are found, they are stored in an array, hash, map or dictionary. Recursive calls can look up results in the array rather than having to recalculate them.

Motivation

Applying this technique into formulas that heavily uses the factorial(n!) of numbers can have a huge performance increase in any algorithm.

Problem

Let's consider a simple factorial equation (x! + y!) / (z! + x!). Where x,y,z are any natural numbers (positive integer) and are not equal to zero. We will solve this equation with and without memoization into consideration.

Solution 1

   let functionCall = 0;
   // factorial function without memoization
   function factorial(n:number){
      functionCall++;
      if(n === 1){
        return 1;
      }

      return n * factorial(n-1);

   }

  // equation solution with factorial function
  const x = 20, y = 15, z = 10
  const result = (factorial(x) + factorial(y)) / (factorial(z) + factorial(x));
  console.log(result);
  console.log(functionCall);

This works well but there is a huge performance issue here because the overall function calls 65 times plus there is always an overhead with recursive operations making them costly.

Solution 2

   // factorial function with memoization

   let functionCall = 0;
   let memo = {};

   function factorial(n:number){

      functionCall++;

      if(n === 1){
        return 1;
      };

      if(memo[n]){
        return memo[n];
      } else {
        memo[n] = n * factorial(n - 1);
        return memo[n];
      }

   }

  // equation solution with memoized factorial function
  const x = 20, y = 15, z = 10
  const result = (factorial(x) + factorial(y)) / (factorial(z) + factorial(x));
  console.log(result);
  console.log(functionCall);

Now this algorithm is efficient because functionCall is now 23 and Why ? because the function calls factorial(x=20) and stores the factorial of all numbers below it in the hash map which looks like this ...

  {
  '2': 2,
  '3': 6,
  '4': 24,
  '5': 120,
  '6': 720,
  '7': 5040,
  '8': 40320,
  '9': 362880,
  '10': 3628800,
  '11': 39916800,
  '12': 479001600,
  '13': 6227020800,
  '14': 87178291200,
  '15': 1307674368000,
  '16': 20922789888000,
  '17': 355687428096000,
  '18': 6402373705728000,
  '19': 121645100408832000,
  '20': 2432902008176640000
}

Now for the other functions in the equation it just looks for the factorial of x,y,z which exist as keys 20, 15 and 10 in the hashmap and returns it instead of recalculating the value again. It doesn't matter the order at which the values passed to the factorial function are called once a value exist on the hash map it doesn't recompute.

Conclusion

Thinking recursively unlocks a world of it own when solving algorithm and improves your thinking capability. By applying memoization we are able to increase the efficiency of the algorithm. Thanks