Number of ways to reach A to B by climbing one step, two steps or three steps at a time

I was solving a test on an online platform and the problem statement was similar to this.

Stuart has to go from one place to other (A-> B) and he can jump either 1 step, 2 step or 3 steps at a time. There can be n number of stoppers between A to B.

We need to find the number of ways he can do this.

I feel this is similar to the classic climb stairs problem with little difference that there you finally had to reach the n-th step whereas in this particular problem you have to get down which makes n+1 step probably. Am I right?

So the code I wrote is this:

function countWays(n) {
    
    if (n < 0) return 0;
    if (n === 0) return 1;
    if (n === 1) return 2; //If you have one stop-over, there's two ways to reach. One is take one jump and then one more. Second is take two jumps at once and reach the destination

    return countWays(n-1) + countWays(n-2) + countWays(n-3);
 
}

console.log(countWays(4))

This didn't get accepted. So I'm just wondering what's wrong in this. Should I have added base case for n==2 as well?

if (n === 2) return 4

This still doesn't do any good though as for n = 3 it would return 6 whereas visually I can see there would be 7 ways if there 3 stop overs.

Another question I want to ask is,

In the classic stair case the base case for n === 0 would be 1. Would it still be the same here? This confuses me a bit as when there's no more step to climb how can the result be 1. On the hand hand here, when n === 1 you still have one way that you must take to reach the destination.

Also, for f(3) the logic and intuition says it should be:

number of ways to reach first stopover + f(2)

And number of ways to reach first stopover would be just one since there's only one way you can do so (by taking one jump.)

However, I can't put if(n == 1) return 1 in the base case as it would be incorrect. Let's say there's only one stop-over (n = 1) there's actually two ways to reach:

1. Jump 2 steps
2. Jump 1 steps and then one more.

So this is also creating a bit confusion.

I feel this is similar to the classic climb stairs problem ... whereas in this particular problem you have to get down which makes n+1 step probably. Am I right?

Yes.

Should I have added base case for n==2 as well?

Yes, or you could more easily add the n == -1 case, because that represents the case where you arrived at the destination, and represents a possibility (1). This looks odd, but it is consistent with your previous observation that the way this problem is stated differs with 1 step compared to the phrasing you were more used to. The case where n < -1 is where you overshoot the destination, and so that is when you want to return 0. You actually don't need other cases than the exact arrival (n == -1) and the overshooting (n < -1). The rest follows from it.

Here is your code adapted:

function countWays(n) {
    if (n < -1) return 0; // Overshooting: not a possibility.
    if (n === -1) return 1; // Destination reached: this is a possibility and thus counts as one.
    return countWays(n-1) + countWays(n-2) + countWays(n-3);
}

for (let n = 0; n < 5; n++) {
    console.log(n, countWays(n));
}

Now this is not efficient, as for larger n, you will make the same recursive calls over and over again. You could use bottom up tabulation to have an efficient solution:

function countWays(n) {
    let [a, b, c] = [0, 0, 1];
    while (n-- > -1) {
        [a, b, c] = [b, c, a + b + c];
    }
    return c;
}

for (let n = 0; n < 5; n++) {
    console.log(n, countWays(n));
}