The Staircase Problem

You’ve now learned to use a new mental strategy for solving certain computational problems using top-down recursion. However, you may still be skeptical and ask, “Why do we need this new mental strategy anyway? I’ve been able to solve these problems with loops just fine until now.”

Indeed, you may not need a new mental strategy for simpler computations. But when it comes to more complex functions, you may find that the recursive mindset makes the writing of code much easier. It certainly does for me!

Here’s one of my favorite examples. A famous question—known as the staircase problem—goes like this:

Let’s say we have a staircase of N steps, and a person has the ability to climb one, two, or three steps at a time. How many different possible “paths” can someone take to reach the top? Write a function that will calculate this for N steps. The following image displays three possible paths of jumping up a five-step staircase.

These are just three of many possible paths.

Let’s first explore this problem with a bottom-up approach. That is, we’ll work our way up from the simplest cases to the more complex ones.

Obviously, if there’s only one step, there’s only one possible path.

With two steps, there are two paths. The person can climb one step twice, or the person can jump up two steps at once. I’ll write this like so:

With a staircase of three steps, someone could take one of four possible paths:

With four steps, there are seven options:

Go ahead and try to draw up all the combinations for a five-step staircase. It’s not that easy! And this is just five steps. Imagine how many combinations there are for, say, eleven steps.

Now, let’s get to the question at hand: how would we write the code to count all the paths?

Without the recursive mindset, it can be difficult to wrap one’s mind around the algorithm for making this calculation. However, with the top-down way of thinking, the problem can become surprisingly easy.

For an eleven-step staircase, the first subproblem that comes to mind is a ten-step staircase. Let’s go with that for now. If we knew how many possible paths there are to climb a ten-step staircase, can we use that as a base for calculating the paths for an eleven-step staircase?

For starters, we do know that climbing an eleven-step staircase will take at least as many steps as climbing a ten-step staircase. That is, we have all the paths to get to stair number 10, and from there, one can climb one more step to get to the top.

However, this can’t be the complete solution, since we know that someone can also jump to the top from stair numbers 9 and 8 as well.

If we think about it further, we’ll realize that if you’re taking any path that includes going from stair 10 to stair 11, you’re not taking any of the paths that include jumping from stair 9 to stair 11. Conversely, if you jump from stair 9 to stair 11, you’re not taking any of the paths that include stepping on stair 10.

So we know that the number of paths to the top will include at least the number of paths to stair 10 plus the number of paths to stair 9.

And since it’s possible to also jump from stair 8 to stair 11, as one can jump three steps at a time, we need to include the count of those paths as well.

We’ve determined, then, that the number of steps to the top is at least the sum of all the paths to stairs 10, 9, and 8.

However, in thinking about it even further, it’s evident there aren’t any other possible paths to the top beyond these. After all, one can’t jump from stair 7 to stair 11. So we can conclude that for N steps, the number of paths is the following:

Other than the base case, this will be the code for our function!

It seems too good to be true that this is almost all the code we need. But it is true. All that’s left to deal with is the base case.

Staircase Problem Base Case

Determining the base case for this problem is slightly tricky. That’s because when this function gets to an n of 3, 2, or 1, the function will call itself on n of 0 or below. For example, number_of_paths(2) calls itself for number_of_paths(1), number_of_paths(0), and number_of_paths(-1).

One way we can deal with this is by hardcoding all the bottom cases:

Another way to devise the base cases here is to cleverly rig the system by using strange but effective base cases that just happen to compute the right numbers. Let me show you what I mean.

We know that we definitely want the result of number_of_paths(1) to be 1, so we’ll start with the following base case:

Now, we know that we want number_of_paths(2) to return 2, but we don’t have to create that base case explicitly. Instead, we can take advantage of the fact that number_of_paths(2) will compute as number_of_paths(1) + number_of_paths(0) + number_of_paths(-1). Since number_of_paths(1) returns 1, if we made number_of_paths(0) also return 1, and number_of_paths(-1) return 0, we’d end up with a sum of 2, which is what we want.

So we can add the following base cases:

Let’s move on to number_of_paths(3), which will return the sum of number_of_paths(2) + number_of_paths(1) + number_of_paths(0). We know that we want the result to be 4, so let’s see if the math works out. We already rigged number_of_paths(2) to return 2. number_of_paths(1) will return 1, and number_of_paths(0) will also return 1, so we end up getting the sum of 4, which is just what we need.

Our complete function can also be written as:

While this is less intuitive than our previous version, we cover all the base cases with just two lines of code.

As you can see, the top-down recursive approach made solving this problem much easier than it might have been otherwise.