This questiion is related to Staircase problem - explanation of recursive approach
But about the base cases.
One variation of the problem is as follows:
There are n stairs, a person standing at the bottom wants to climb stairs to reach the nth stair. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.
the base condition goes like this:
if( n <= 1) return n
Makes sense as when there's 1 step, there's only one way to climb. So is the case in which there's 0 steps to climb.
But in the variation of the same problem, where the person can take 1, 2 or 3 steps, the base becomes like this:
if(n<0)
return 0;
if(n == 0)
return 1;
So if there are 0 steps to climb there's one way here. Why?
Another thing I notice, there's emphasis on negative n in the latter case, i.e it has to return 0 in that case while in former it's not explicitly handled. Does it not occur in former?
It's like Fibonacci. If f(n) is the number of ways of climbing up n steps, and we can take up to k at a time, then f(n) = f(n-1) + f(n-2) + ....+ f(n-k), where f(0) = f(1) = 1, and f(anything negative) is 0.
The reason is, every combination of steps which leaves us at n has a last step of size 1 or 2 or 3 or ... or k, except if n is less than k then we ignore or treat as 0 anything from n+1 up to k.
e.g., if k=3 and f(n) is the number of ways of reaching the n'th step, then f(7) either ends with a size 1 step in f(6) ways, a size 2 step in f(5) ways, or a size 3 step in f(4) ways.
But, f(2) can't end with a step of size 3, so we can either only calculate f(0) + f(1), or treat f(anything negative) as being 0. The former is slightly more efficient, the latter is simpler.