How to Solve the Staircase Problem with 5 Lines of JavaScript
Tags: javascript, programming, leetcode, algorithms
Published: 2022-07-20 01:06:39

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

![scared cat](https://i.imgflip.com/6m6pa9.jpg)

### 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...

```javascript
// 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 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):

```javascript
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:

```javascript
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 :**
```javascript
  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.

5. 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:

```javascript
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](https://indepthjavascript.dev/how-to-solve-the-staircase-problem-with-javascript-using-memoization)

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

If you enjoyed this article, please check out my blog [Indepth JavaScript] (https://indepthjavascript.dev/) for more illuminating content. 🤓