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

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:

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

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:

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