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:

- 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);
- 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.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array