# Staircase recursion problem in JavaScript

Let's assume that we can climb a staircase walking 1, 2 or 3 steps.

`staircase = 1`

```terminal```|---
|

There is 1̲ option to climb the staircase:

1
``````

`staircase = 2`

```terminal```
|---
|---|
|

There are 2̲ options to climb the staircase:

1, 1
2
``````

`staircase = 3`

```terminal```
|---
|---|
|---|
|

There are 4̲ options to climb the staircase:

1, 1, 1
2, 1
1, 2
3
``````

We can see that:

```javascript```
stepPerms(1) = 1
stepPerms(2) = 2
stepPerms(3) = 4

``````

## What happens if the staircase is greater than 3?

`staircase = 4`

```terminal```
|---
|---|
|---|
|---|
|

We have 7̲ options to climb the staircase:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
3, 1
1, 3
``````

We can see that:

```javascript```stepPerms(4) = stepPerms(3) + stepPerms(2) + stepPerms(1) = 7
``````

If we calculate the number of options for `staircase = 5`, `staircase = 6`, `staircase = 7`, we we'll conclude:

```javascript```stepPerms(n) = stepPerms(n - 1) + stepPerms(n - 2) + stepPerms(n - 3)
``````

Let's translate this formula into code!

## First approach

We can use a recursive approach to solve the problem.

```javascript```function stepPerms(n){

if(n === 1) return 1;
if(n === 2) return 2;
if(n === 3) return 4;
if(n  >  3) return stepPerms(n - 1) + stepPerms(n - 2) + stepPerms(n - 3);

}
``````

This approach works fine but it's not time efficient as we are calling the function recursively.

## Second approach

Instead of using recursion, we can calculate the results in real time.

```javascript```function stepPerms(n) {

if(n === 1) return 1;
if(n === 2) return 2;
if(n === 3) return 4;

if(n  >  3){

let steps = [0, 1, 2, 4];

for(let i = 4; i <= n; i ++){

steps[i] = steps[i - 1] + steps[i - 2] + steps[i - 3];

}

return steps[n];
}

}
`````` Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.