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];
    }

}