# Count ways to reach the n stair

**Problem statement**

There are stairs, a person standing at the bottom wants to reach the top. The person can climb either stair or 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 step, then we need to solve the problem for stairs. That is, *finding the number of ways to traverse the remaining stairs*. If the person were to take steps then the problem gets reduced to *finding the number of ways to traverse the remaining stairs*. Assuming we have a function `count(n)`

that returns the number of ways to traverse stairs, we would have:

1 |
answer = count(n-1) + count(n-2) |

Finally, we need to define our termination conditions:

If there only stairs left, we know that a person can traverse them in three different ways ( or or ). If there only stairs left, we know that a person can traverse them in two different ways ( or ). If there is only 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: ).

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

function:

1 2 3 4 5 6 7 |
public static int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n-1) + fibonacci(n-2); } } |

Putting it all together we have:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class NumberOfWays { public static int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n-1) + fibonacci(n-2); } } public static int count(int s) { return fibonacci(s + 1); } public static void main (String args[]) { int s = 4; System.out.println("Number of ways = "+ count(s)); } } |