Recursion, Memoization, and the Staircase Algorithm

Photo by Serhat Beyazkaya on Unsplash

Before we get into those definitions, let’s dive into the Leetcode problem that started it all: The Staircase Question.

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

This problem seems simple enough at first. You think about it for a little bit and come up with some basic principles:

input: n = 1
output: 1
// 1 step
-----------------------
input: n = 2
output: 2
// 1 step + 1 step
// 2 steps
-----------------------
input n = 3
output: 3
// 1 step + 1 step + 1 step
// 2 steps + 1 step
// 1 step + 2 steps

Not so difficult. But what happens when you have a 40 stair staircase? Not only will your quads be burning, but you’ll also get so many branching-path decisions.

The Thought Process

The crux of this problem opens up when you ask yourself this simple question: “from which steps can I reach the nth step?”

The nth step can only be reached from the n-1 and n-2 steps, because that is the largest you are able to step from. So, if we added up all the ways it takes us to get to n-1 steps and add that to all the ways it takes us to get to n-2 steps, we should get our answer! Ex: If n = 4, all we would need to do is add n = 3 and n = 2to get our answer. And with those two paths, we can narrow those down even further.

Representation of n=4 steps

The Naive Solution

All of this repetition and narrowing down to a singular case is starting to sound familiar. Looks like we’re about to get a visit from our good friend recursion.

For those who don’t know recursion, Beau Carnes at FreeCodeCamp wrote an excellent article explaining the basics that you can read here. For now, I’ll go over the bare minimum as a refresher.

In recursion, you need a base case, and a recursive case. The base case tells you when to stop calling your function (aka, we know if n=1, we’ll always return 1). The recursive case calls itself and changes the input, so we narrow it down to the base case.

Here’s the basic code for a naive solution:

function climbStairs(n) {
    if (n === 1 || n === 0) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2)
}

That’s it! There is one problem, however. This recursion takes a lot of time. And by a lot, I mean A LOT. Let’s look back at our diagram.

Recursion Tree

You’ll notice that the 2 circled portions of the tree are the exact same and will return the same value. As n grows, pretty soon we’ll have thousands of those smaller functions being repeatedly called over and over again. If only there were a way to tell the function to memorize the values for larger and larger inputs, so we don’t have to deal with the same function being called many times. Enter memoization.

Memoization

Turns out, there IS a way for our function to remember answers to previous recursion loops. Memoization is the process that keeps track of exactly that. Because searching in an object takes relatively little time, if we kept the input/answer as key/value pairs in an object, we could keep track of our loops and drastically speed up our runtime.

All we have to do is use a helper function that checks our memo object for the value of n. If it finds it, great! If not, we can still do recursion and go further down the loop. This just makes sure we’re not repeating huge swaths of recursive code.

Here’s what it looks like:

climbStairs() with memoization

You can see we declare a memo object and a helper function to do our recursion. Line 6 checks to see if our current value of n is already in our memo. If so, it sets the value of value to be that, and then returns said value on line 16. However, if we don’t know the value, we can just repeat our original recursion code block (lines 9–13). Finally, we make sure to update our memo with this new value that we found. In the end, on line 18, we call our helper function with the original n which will return us the answer we seek.

Conclusion

While the stair problem seems abstract and confusing at first, once you break it down into a simple recursion problem, it becomes much more manageable. Finally, breaking down our slow recursion with memoization drastically improves the time complexity on that function. Thinking about it, each time n increases, we’re almost DOUBLING the amount of function calls we have to make. With memoization and the quick accessing of Javascript objects, we change our time complexity from about O(1.68ⁿ) to O(n). That’s a HUGE difference. For example, the difference between 40 steps and 41 steps is about 60,000,000 different combinations.

That’s it for this problem. As always, feel free to leave a comment and talk about your own journey with recursion or memoization. Thanks for reading!

More content at plainenglish.io