# What is Memoization in Javascript?

## The basis of memoization and a simple use case implementation

Have you ever had to write a pure function where it had to calculate the same input multiple times on different occasions? Didn’t you wish there was an easy way to remember and retrieve those past results without having to recalculate the value every single time?

# Memoization is an Optimization Technique

In programming terms, that’s all it really is. It is a technique or practice which aims to increase a function’s performance by caching previous results. Those results can be retrieved if they exist, otherwise the function will compute the new argument, whose new results will be cached into a collection. Whereby time is traded for space to boost cpu performance.

With the rise of functional programming in Javascript, it is more commonly used with recursive functions. Since such functions can be load intensive.

# Recursive function without memoization

Let’s take a look at this simple recursive function:

`const factorial = num => {  // termination case  if (num < 0) {    throw new Error("Number must be positive.");  };  // base case  if (num === 0 || num === 1) {    return 1;  };  // recursive case  return num * factorial(num - 1);};// Invoke the functionfactorial(3) // 6 factorial(4) // 24`

So we know that the factorial of the value 3 is 6, and 4 is 24, etc. We know the factorial function works based on its argument and nothing else. So ask yourself this: Would there be a performance hit if you had a large input value you had to compute many times? Is there a magic box somewhere someplace to store the result for each input to return if it was created some time ago in the past? How could we implement it for this scenario without relying on an external database?

# Memoize can be a special Higher Order Function

Let’s write a memoize utility function to keep track of our results:

`const memoizeUtil = func => {  // results store  const cache = {};  return (input) => {    // return the value if it exists in the cache object    // otherwise, compute the input with the passed in function and              // update the collection object with the input as the key and    // computed result as the value to that key    // End result will be key-value pairs stored inside cache    return cache[input] || (cache[input] = func(input));  };};`

In the above code, all our results will be stored inside the cache object. This would be the magic box that stores the results!

Then using closure, we are able to either:

A) Return the value if it exists in the cache where it is looked up by the input argument.

B) Otherwise, compute the input with the passed in function and update the collection object with the input as the key and the computed result as the value to that key. The end result will be key-value pairs stored inside the cache.

# Recursive Function with Memoization

Next in order to utilize our memoize function, what we have to do is wrap our factorial function into our memoize utility function so that it will be able to remember its past outputs:

`const findFactorial = memoizeUtil((num) => {  // termination case  if (num < 0) {    throw new Error("Number must be positive.");  };  // base case  if (num === 0 || num === 1) {    return 1;  };  // recursive case  return num * findFactorial(num - 1);})`

We can alternatively write the above in this fashion as well to stay organized:

`const findFactorial = memoizeUtil(factorial)function factorial(num) {  // termination case  if (num < 0) {    throw new Error("Number must be positive.");  };  // base case  if (num === 0 || num === 1) {    return 1;  };  // recursive case  return num * findFactorial(num - 1);}`

Invoke our wrapped factorial function from above to find the results:

`findFactorial(2) // 2findFactorial(3) // 6findFactorial(6) // 720// Current cache object with stored values: {2: 2, 3: 6, 6: 720}findFactorial(6)// Returned value from cache object: 720findFactorial(5) // 120// Current cache object with stored values: {2: 2, 3: 6, 5: 120, 6: 720}`

# Test Memoization by Performance

We can run a timer by utilizing console.time() and console.timeEnd() and wrapping the desired function call between the two. Let’s take a look:

`console.time('factorial test no memo');findFactorial(6) // 720console.timeEnd('factorial test no memo');factorial test no memo: 0.110ms--console.time('factorial test with memo');findFactorial(6) // 720console.timeEnd('factorial test with memo');factorial test with memo: 0.019ms`

As you can see from the above, there is clearly a speed performance by using this special technique. Let’s test this further by inputting a larger value to calculate:

`console.time('factorial test no memo');findFactorial(100) // 9.33262154439441e+157console.timeEnd('factorial test no memo');factorial test no memo: 0.264ms--console.time('factorial test with memo');findFactorial(100) // 9.33262154439441e+157console.timeEnd('factorial test with memo');factorial test with memo: 0.021ms`

Again, the performance gain is clear and its benefits truly shine the larger your calculations become / the larger your stack in a recursive call. While the computational times may vary somewhat across a range of computers, the gain will still exist.

Console.log Test

In a separate test where I did console.log for the return value of findFactorial(100) — It took a whopping 2~4 seconds without memoization and averaged 100~300 milliseconds with memoization. That’s crazy!

# Conclusion

After implementing memoization to the recursive factorial function, you’ll notice not much has changed and it mostly still works like the original. Though now from the perspective of performance, it runs much faster than without using memoization using repetitive inputs.

Though remember that this technique should only be applied to pure functions which have no side-effects (versus impure functions), so results are more predictable. Since the point of memoizing is storing data in memory with a look-up table so it can be access at a later point, the advantages are noticeable for load intensive computations.

What else could you do if you had more than one argument? What if you wanted to memoize the recursive Fibonacci sequence? Give it a try!

## More from Mike

Software Engineer

## Better Monitoring In Development Environment By Aggregating Logs

Get the Medium app