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

Understanding Memoization in JavaScript - Philip Obosi

Introduction to Memorization in JavaScript - Joseph Chege