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.
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
Since 4 is called first, we need to find it’s solution first. When passed 4 we end up calling
climbStairs(2). Handling 3 first, we end up calling
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(2). But as your starting number increases, the number of repeat calls grows exponentially.
climbStairs(6), you end up calling
climbStairs(3) 3 times,
climbStairs(2) 5 times, and
climbStairs(1) 3 times.
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:
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, we set
memo to equal
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
climbStairs(3) doesn’t find
memo and sets it to
memo do exist,
memo, or just 1.
memo or just 2.
This takes us back to
climbStairs(3), where we set
memo to 2 + 1, or 3. We then return memo. This sends us back into
climbStairs(4) where we set
memo to the return of
climbStairs(3) // 3 and
climbStairs(2) // 2.
memo now equals 5, and we return
memo to our initial call of
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 to equal 3. Now instead of calling
climbStairs(1), we simply return 3. That’s one array index lookup instead of two function calls and one operation. We set
memo to 5 + 3, and return
memo 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: