Learning Memoization

In this post I'll be discussing what memoization is as well as when to use it.

What is Memoization?

Memoization at its core is the process of greatly decreasing the run time of expensive recursive or iterative function. More specifically, memoization stores and reuses precomputed values while passing them through recursive calls to improve the speed of your algorithms.

Why Use Memoization?

A great example of how and why to use memoization can be seen when creating a function to create the Fibonacci sequence.

If you're not familiar, the Fibonacci sequence starts with 0 and 1, all further values are calculated by adding the previous two values. 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, etc.

This function is often made recursively like so.

When calling this function on small numbers it is relatively quick, but when we call it on large numbers the runtime will drastically increase. This is due to each call of fibonacci() doing the same amount of work, regardless of it was already run or not. The function is repeatedly doing the same calculations over and over again!

How to use Memoization?

Instead of doing wasting time by doing the same work over and over again let's instead store the result of the work in case we need to use it again. In this case we can use a simple hash map to track what numbers have been computed and what results we got from the computations.

Our main function contains our map that stores computed values as well as another function. This inner function checks if our hash contains the result of the called number, otherwise it does the fibonacci function from the original example. By doing this method we avoid any unnecessary work.

Conclusion

Hopefully you now understand the basics of memoization. However, in this example we only really scratched the surface. Memoization gets much more complicated when the function needs to handle multiple arguments or store objects passed as arguments. In my next post I'll go over some more complicated scenarios and how to deal with them.

Thanks for reading! The code used in this post can be found here.