Solving The Staircase Problem With Just 5 Linesby@indepthjavascript

# Solving The Staircase Problem With Just 5 Lines

July 21st, 2022

Staircase Programming Challenge: How many different ways can you reach the top of the stairs? How many ways you can take 1, 2, or 3 steps at a time? There is a simple way to solve this problem using everyone's favorite algorithm: **recursion. Here is the solution in 5 lines of JavaScript code: stepTaken is a counter for steps taken in each combination. It's tricky for sure, but once you understand it, it opens up a whole new world of possibilities!

### Company Mentioned

If you're new to algorithms and leetcode, the staircase problem is infamous!

😬

## What is the Staircase Programming Challenge?

Stated simply....

Imagine a staircase with `N` steps. If you can take 1, 2, or 3 steps at a time, how many different ways can you reach the top of the stairs?

Encountering a problem like this for the first time is for sure frightening. Even on its own as a math problem, IT'S REALLY HARD.

There are a few obvious cases. You can take 1 step at a time, `N` times. If `N` is divisible by 2, you can take 2 steps, `N/2` times. Also, if `N` is divisible by 3, you can take 3 steps, `N/3` times.

And then there is everything in between. 🤔

The good news is there is a really simple way to solve this problem using everyone's favorite algorithm: recursion. 😨

## Recursion to the Rescue

As promised, here is the solution in 5 lines of JavaScript code...

``````// N is total number of steps in the staircase
// stepTaken is a counter for steps taken in each combination
function steps(N, stepsTaken = 0) {

if (stepsTaken === N) return 1;
else if (stepsTaken > N) return 0;

return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);
}
``````

### Yikes! What does this mean??

Don't panic or feel bad if the above code confuses you. I struggled for a long time with recursion since I first learned it in high school CS class. It's tricky for sure. But once you understand it, it opens up a whole new world of possibilities!

## Let's walk through this solution

If you're thinking of just copying the above solution and leaving, you're missing the point. It's super important you understand what's happening.

`function steps(N, stepsTaken = 0)` is just a simple recursive counter.

Let's walk through it:

1. We're at the bottom of the stairs, no steps taken. So `stepsTaken = 0`.

2. You have 3 possibilities in front of you: take 1 step, jump up 2 steps, or leap up 3 steps.

3. Now we need to account for ALL 3 possibilities. So imagine you clone the stairs and yourself 2 times. Plus, you each have your own version of `stepsTaken` variable you’re carrying with you. You and your clones each go through one of these 'doors' (note each of you must go through a DIFFERENT door):

``````steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)
``````

Once you go through your chosen door, your individual `stepsTaken` counter will be incremented by 1, 2, or 3 (depending on the door you went through). Then after that, you'll immediately see 3 more doors:

``````steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)
``````

Again, you'll clone yourself 2 times again and each go through one of these `steps` doors. Your `stepsTaken` counter will increment again by 1, 2, or 3. This will KEEP HAPPENING until:

``````  if (stepsTaken === N) return 1;
else if (stepsTaken > N) return 0;
``````

If you overstepped `stepsTaken > N`, your combination of steps does NOT count towards the total of unique ways to go up the stairs.

However, `if (stepsTaken === N)`, then bingo 🤩 you found a legit combo of steps to go up the stairs, and you `return 1` to add to the count of ways to go up the stairs.

1. Now remember the way we count the number of possible combinations of `stepsTaken` to reach the top of the `N` step staircase is to simply add all the possibilities:

``````return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);
``````

Remember each legitimate combo of steps where `if (stepsTaken === N) return 1` and each if path is not valid (overstep) then 0 is returned : else `if (stepsTaken > N) return 0`.

Some of you may be asking: Nice, this is elegant, but isn't it super inefficient in terms of time complexity?

Yea, it's super high time complexity. However, there's a trick to dramatically improving that ➡️ How to Solve the Staircase Problem with JavaScript using Memoization

Hope this makes sense, comment below if you have any questions?