[Solved] How many ways to go up a N-step stairs?

by


The answer by Code-Apprentice is very good, so I want to contribute a different approach:

Writing down the solutions for the first few flight of stairs I quickly noticed a pattern. Let’s see:

total steps | steps taken   | ways to go up
------------x---------------x--------------
1           | 1             | 1
------------x---------------x--------------
2           | 2             | 2
            | 1, 1          |
------------x---------------x--------------
3           | 3             | 4
            | 2, 1          |
            | 1, 2          |
            | 1, 1, 1       |
------------x---------------x--------------
4           | 4             | 8
            | 3, 1          |
            | 2, 2          |
            | 2, 1, 1       |
            | 1, 3          |
            | 1, 2, 1       |
            | 1, 1, 2       |
            | 1, 1, 1, 1    |

So apparently for a flight of stairs with N-steps, there’re 2^(N-1) ways to go up.
We don’t even need recursion!
This solution is a lot quicker to execute and easier to maintain, but since you’re trying to understand recursion, Code-Apprentice’s answer is the way to go.

1

solved How many ways to go up a N-step stairs?