Basic JavaScript Memoization
If you’re new to JavaScript, there’s a good chance you’re using a website like LeetCode or HackerRank to improve your algorithm skills. A big part of this is getting better at using both recursion and iteration to solve problems. One trick that can greatly improve your recursive solutions is a technique called memoization.
Memoization is just a way to store the results of function calls. This is incredibly helpful in functions that end up getting called with the same arguments over and over. If your function is pure, and the same input always returns the same output, then it wouldn’t make sense to call the function with the same input multiple times.
The simplest way to implement memoization is just by passing an object along with your function calls. I was able to use this method to recursively answer a LeetCode problem, that would otherwise time out. Imagine you’re climbing a set of stairs, and you’re given the amount of steps to the top. If you can take either one or two steps at a time, how many different ways are there to get you to the top? The result ends up being a fibonacci sequence from 3 steps onward. This means the return value of 3 steps will be the sum of 2 steps and 1 step, the return value of 4 steps is the sum of 3 steps and 2 steps, and so on. The JavaScript code to implement this recursively could look like this:
This works, but not well. The problem here is how long it takes to complete the operations. When you call climbStairs(5), in order to return it calls climbStairs(4) and climbStairs(3).
Since 4 is called first, we need to find it’s solution first. When passed 4 we end up calling climbStairs(3) and climbStairs(2). Handling 3 first, we end up calling climbStairs(2) and climbStairs(1). Finally, those function calls return us 2 and 1. We add them together, and the output of climbStairs(3) is 3. Now, back inside climbStairs(4), we add the return of climbStairs(3) // 3 and climbStairs(2) // 2, so climbStairs(4) equals 5.
Now we’re back at our original function call again, climbStairs(5). We have our first return from climbStairs(4) // 5, and now we need to calculate the second half, climbStairs(3). But we’ve already calculated that before! We know it returns 3, but since our function doesn’t, it ends up running all the calculations again. In this instance, instead of returning 3, it’s just climbStairs(1) and climbStairs(2). But as your starting number increases, the number of repeat calls grows exponentially.
When calling climbStairs(6), you end up calling climbStairs(4) twice, climbStairs(3) 3 times, climbStairs(2) 5 times, and climbStairs(1) 3 times.
Calling climbStairs(7) calls climbStairs(5) twice, climbStairs(4) 3 times, climbStairs(3) 5 times, climbStairs(2) 8 times, and climbStairs(1) 5 times. That’s a lot of wasted computations.
The solution here is memoization. If we pass a cache along that contains answers to each value we’ve already passed in, we can check it for a solution to prevent repeating lengthy calculations. The implementation could look like this:
Lets call climbStairs(5) once more. Here, on our initial call, we instantiate our memo object, (or array in this instance), with our smallest values that do not follow the fibonacci sequence. The first part of our code behaves very similar to our last solution. Since there is no memo[5], we set memo[5] to equal climbStairs(4) + climbStairs(3), passing the memo object along with our calls. This calls climbStairs(4) first, which again doesn’t exist in our memo, so we set memo[4] to climbStairs(3) + climbStairs(2). climbStairs(3) doesn’t find memo[3] and sets it to climbStairs(2) + climbStairs(1). Since memo[1] and memo[2] do exist, climbStairs(1) returns memo[1], or just 1. climbStairs(2) returns memo[2] or just 2.
This takes us back to climbStairs(3), where we set memo[3] to 2 + 1, or 3. We then return memo[3]. This sends us back into climbStairs(4) where we set memo[4] to the return of climbStairs(3) // 3 and climbStairs(2) // 2. memo[4] now equals 5, and we return memo[4] to our initial call of climbStairs(5).
So far, we haven’t saved ourselves any time. But now we hit the second half of climbStairs(5), and call climbStairs(3) again. Since we’ve already called climbStairs(3), we’ve already set memo[3] to equal 3. Now instead of calling climbStairs(2) + climbStairs(1), we simply return 3. That’s one array index lookup instead of two function calls and one operation. We set memo[5] to 5 + 3, and return memo[5] which holds our final answer of 8.
Starting with a small number like 5 hasn’t really improved our solution at all. In fact all it did was add extra memory to our solution. This is something you must keep in mind when memoizing. If you’re not calling functions with the same values often, it might not be worth memoizing. But when you start with a much larger number, you end up cutting out exponentially more calculations.
When using the memoized method on climbStairs(7), you still end up calling climbStairs(5) twice, but you only call climbStairs(4) twice instead of three times, climbStairs(3) is also only called twice instead of 5 times, climbStairs(2) is only called twice instead of 8 times, and climbStairs(1) is only called once.
This is a decent savings in the number of operations you’re performing, even with a relatively low starting number. And as you increase your initial value, you’ll still only be performing each calculation at most 2 times. This keeps the algorithm performant, even with larger numbers.
And the proof is in the pudding. If you try to solve the problem on LeetCode with the first solution, the test environment will time out. With the second solution it passes the tests. You can get an idea of why by wrapping each function call between a console.time() and a console.timeEnd(). This will implement a counter to give you a basic idea of how long a function takes to complete. console.time('arg') starts a timer, and the time elapsed is returned with console.timeEnd(‘arg’). It’s not extremely accurate, but can help you see larger discrepancies between functions:
Here we can see that we can call the memoized and the non-memoized versions of the function on a small number like 7, the speed is in milliseconds for both, and memoization makes little difference in completion time, and may even be slower. But when tested with a number like 45, the time goes from milliseconds for the memoized version, to over 9 seconds for the non-memoized version. The difference speaks for itself. In a situation where you had to repeatedly run a function like this, you could be wasting a ridiculous amount of time.
Of course there is a downside to memoization as well. Each value you store in your memoize object takes up memory. If you never end up calling a function with the same input more than once, you’re creating an extra step in storing that return value and never getting the benefit of using that value to prevent unnecessary operations. This would waste extra time and space, and would ultimately be less performant than the original brute force recursive solution. Having a good idea of what data is being passed into your function is crucial to memoization performance.
This is about as simple an example of memoization as you can have. To be more abstract / practical, you could have a memoization function that you pass another function into. The memoization function could then automatically add a memoization object and recursively call the function you passed in, making memoization easily accessible across your environment. You can read more about memoization here:
Memoization in JavaScript - Anish Kumar
