Search code examples
algorithmrecursionfibonaccirecurrence

Staircase problem - explanation of recursive approach

The problem goes like this:

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.

So the explanation goes like this:

The person can reach nth stair from either (n-1)th stair or from (n-2)th stair. Hence, for each stair n, we try to find out the number of ways to reach n-1th stair and n-2th stair and add them to give the answer for the nth stair. Therefore the Recurrence relation for such an approach comes out to be :

ways(n) = ways(n-1) + ways(n-2)

How does that work? Here's my question:

  1. If the person is at n-1th step, shouldn't they still need one more steps making the first parameter ways(n-1) +ways(1);
  2. And if they're at n-2th step, they would need ways(2) more steps to climb the top.

I know the solution is valid but somehow I'm unable to wrap my head around this.

Solution

  • What we are counting is the number of ways to get to the nth floor, not the number of steps its takes us to get there.

    Imagine we represent one way to get to the nth floor by a list of steps, each step being represented either as 1, for one-step climb, or 2, for the two-step climb. Whatever the length of this list, it represents one way of getting to the nth floor.

    We could now write a function which, given n, would return a list of all such possible distinct lists of steps. This list's length is the number of ways the problem asks about. Again, the length of each member list doesn't matter, just that they are all distinct.

    The explanation is lacking. A clearer one IMO would be, "The person can reach nth stair by 1 more step from either (n-1)th stair (making one climbing step of 1 stair) or from (n-2)th stair (making one step of climbing 2 stairs)."

    Still this explanation seems backwards to me. I would rather prefer:

    • We have to go n stairs up. Either we climb one stair, in which case we have n-1 more stairs to go; or we climb two stairs, in which case we have n-2 stairs to go. So we combine the two:

      ways(n) = ways(n-1) + ways(n-2)

    The formula is the same, but now the intent is immediately clear.

    What creates the multiplicity of ways is the choice.

    See also: this related answer of mine. Also, this one and its links.