## [f]izzbuzzer

### Looking for good programming challenges?

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

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