# 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:

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:

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:

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