### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Count ways to reach the n stair

Sharing is caring!

Problem statement
There are $n$ stairs, a person standing at the bottom wants to reach the top. The person can climb either $1$ stair or $2$ stairs at a time. Count the number of ways, the person can reach the top.

Solution
We can solve this problem recursively. If the person were to take $1$ step, then we need to solve the problem for $n-1$ stairs. That is, finding the number of ways to traverse the remaining $n-1$ stairs. If the person were to take $2$ steps then the problem gets reduced to finding the number of ways to traverse the remaining $n-2$ stairs. Assuming we have a function `count(n)` that returns the number of ways to traverse $n$ stairs, we would have:

Finally, we need to define our termination conditions:
If there only $3$ stairs left, we know that a person can traverse them in three different ways ($1+1+1$ or $1+2$ or $2+1$). If there only $2$ stairs left, we know that a person can traverse them in two different ways ($1+1$ or $2$). If there is only $1$ stair left, we know that a person can traverse them in one way only. These are our recursion-termination conditions.

• `count(3) = 3`
• `count(2) = 2`
• `count(1) = 1`

Above we can see that `count(n)` is actually equal to `fibonacci(n+1)`:

• `count(3) = fibonacci(4) = 3`
• `count(2) = fibonacci(3) = 2`
• `count(1) = fibonacci(2) = 1`

(Remember: $f_0 = 0, f_1= 1, f_2 = 1, f_3 = 2, f_4 = 3, \dots$).

We can solve this problem using the fibonacci series. Let us go ahead and define our `fibonacci(n)` function:

Putting it all together we have: