Staircase problem - Varying base cases in different coditions

Question

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?

Answer 1

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.

Answer 2

Thinking equationally is easier. Not "what to do?", but "what is it?". Not to concern ourselves with the outcomes of conditional expressions and whether they come out right or wrong, but instead just write pseudocode equations for the specific cases, and translate into the real code later:

#number of ways      #all ways
f(0)  =  1           g(0)  =  [ [] ]
f(1)  =  1           g(1)  =  [ [1] ]
f(n+2) =             g(n+2) =  [ [1, ...xs]  FOR xs IN g(n+1) ] ++
 f(n+1) + f(n)                  [ [2, ...xs]  FOR xs IN g(n) ]

There's no more steps to go climbing when there's 0 more stairs to go.

There's one more step to go climbing when there's 1 more stairs to go, by a 1-stairs climbing step, and

there's one more step to go climbing when there's 2 more stairs to go, by a 2-stairs climbing step.