# How to Solve the Staircase Problem with 5 Lines of JavaScript

## Fun with Algorithms

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:

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

. - You have 3 possibilities in front of you:
*take 1 step, jump up 2 steps, or leap up 3 steps.* - 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 your 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 way 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 way to go up the stairs.- 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?