Memoization and Recursion
In a previous blog post I wrote (here), I talked about how important it was to determine the runtime complexity of the code you use to tackle problems. Developers are always looking for the most efficient solution. In some cases, the solution you come up with immediately is not the most performative one and you will want to rewrite the code completely; in other cases, however, you do not necessarily have to completely scrap the code you wrote initially.
Let’s take the Fibonacci algorithm as an example. The Fibonacci series is an ordering of numbers where each number is the sum of the preceding two. The sequence:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
forms the first ten entries of the Fibonacci series. One common algorithmic problem is to print out the nth entry in the Fibonacci series. For example, we would want:
fib(6) === 8
One way to solve this algorithm is to use Recursion, which is when a function calls itself until some condition is met to stop it. This is useful in situations when one action can be divided into multiple identical tasks that are simpler.
If we solve this with recursion, this is what we would get:
Notice that the only time we return a discrete number in this solution is if our input number is less than 2; that is our “base case”. When we call fib(0), we return the number 0 and when we call fib(1), we return the number 1.
If our input is any other number, we will enter our recursion. What happens then? A diagram helps to illustrate the process if we call fib(5).
So. The first thing that happens is we check to see if we have satisfied our base case…is our input (5) less than 2? It is not! So we enter our recursive step, which means we now will call fib(4) and fib(3)…in other words, we have taken one function call and created two function calls from it. We check to see if those calls satisfy our base case and they do not. We make two more function calls for each of those and check to see if each of those has satisfied the base case and for any one that has not, two more function calls get created. And this goes on until there are no more functions that do NOT satisfy our base case, which for our example is n < 2. The only time actual numbers are returned is when that base case is met, and those numbers will be added together. We don’t really care about 0, so if we add all the 1s together in our example (the boxes with the red stars in the image above), we get 5. This means that calling fib(5) gives the number 5, which should be the number at index 5 of the Fibonacci series. And it is!
You can probably already start seeing some issues here. Recursion might work well for this problem if the n stays relatively small…but what happens when we want to print out a number farther along in the series? The runtime for fib(1), fib(2), fib(3), fib(4) is around 1 millisecond…but already by about fib(15) it jumps to around 1000 milliseconds, or 1 second. That’s a huge jump in runtime for a not so huge jump in input!
So what’s happening here? Well, let’s take a look at our diagram for a call of fib(5) again. We are calling the function a total of 15 times to get our output. If we draw a similar diagram for fib(6), so we just increase our input by 1, the function will be called a total of 25 times. This is the very definition of Exponential Runtime, or O(2^n). For each additional element that we add into our function, there is a dramatic increase in the number of function calls required.
We do NOT like this. This is an automatic NOPE!
Does this mean we are doomed to a life of exponentially increasing runtimes trapping us in what seem like ENDLESS SECONDS of waiting around for our function to tell us what the nth entry of the Fibonacci series is???
**cue dramatic music**
Thankfully, the answer to that is another NOPE.
There are two ways of handling this issue:
Scrap the recursion and go with an Iterative Solution!
If we solve this using an iterative solution, this is what we will get:
Based on what we learned in my runtime complexity article, we have a simple for loop that iterates over one fixed collection…this would be Linear Runtime complexity, or O(n). Fantastic!
Don’t be a quitter and stick with recursion!
Ok, so in most cases, you’ll want to go with the iterative solution. Recursion is often NOT the best approach. However, for those developers having to go through job interviews it is VERY important to know how to improve on the recursive solution…and it’s just generally a good idea to understand how to go about thinking through a problem like this.
So what if we wanted to improve the recursive solution?
Let’s look at our fib(5) diagram again, but this time let’s gray out the duplicate function calls…the functions called with the EXACT SAME arguments.
There’s a lot of redundancy there! We make a fib(3) call twice, a fib(2) call three times and a fib(1) call four times…and you can just imagine the repetition when we call our function with larger numbers. Ideally, we’d like to do the calculations for our function calls only once. Is there a way to achieve this? Yes! It’s called…
Memoization
What would be ideal is if we could store the arguments of each function call along with the result. Then, if the function is called again with the same arguments, we can just go ahead and return the pre-computed result, rather than running the function again. This is the concept behind memoization.
The whole idea here is to declare some kind of storage area, some place where we can record all the arguments used to call a function and the respective results from all those function calls.
So we can create a memoize function that will handle storing results and returning those stored results…this function will be responsible for calling the recursive function.
The function memoize(fn) will accept a function as an argument…the function that we will want to ‘speed up’. In our case, it will be our slowFib function; but the way we’ve written memoize(fn), it’s generic enough that we could use it for ANY function we’d want to speed up.
Notice that cache = {}. That’s the heart of memoization…somewhere where we can store the arguments passed into our function and the corresponding results of those function calls. So now we return an anonymous function that is responsible for checking to see if the arguments passed into our slow function are present…if they are, the results immediately get returned and the function stops there. If not, if we get past that first if statement, that means we’ve never used those arguments before. Our memoize function at that point runs our slow function with whatever arguments were passed in and adds those results to the cache.
Notice the line
This is how we connect all the dots. We assign our memoize function with its argument of our “slow” function (slowFib in our example) to a variable, in this case fib. And then we can do something like fib(15)…which will result in a sped up function that will take a lot more than 1000 milliseconds to run! In fact, it takes almost the same amount of time as running fib(4) or fib(5)!
Just to make something clear, though. The fib calls within the slowFib function are NOT a reference directly to the function they are in anymore.
They now reference the memoized function. The memoized version is the version that must be called recursively…if not, we will always have a slow function!
So a better way to write this would be:
And that’s a basic intro to memoization! Hope that helped!