# Distinct ways to reach the n’th stair

Problem: Given stair case with n stairs, count the number of ways in which you can climb the stairs. Each time you can either take 1 step or 2 steps.

Solution:

---
Number of stairs = 1
Ways to climb = (1)
Ways(1) = 1
---
Number of stairs = 2
Ways to climb = (1,1), (2)
Ways(2) = 2
---
Number of stairs = 3
Ways to climb = (1, 1, 1), (2, 1), (1, 2)
Ways(3) = Ways(2) + Ways(1) = 3
---
Number of stairs = 4
Ways to climb = (1, 1, 1, 1), (1, 2, 1), (2, 1, 1), (1, 1, 2), (2, 2)
Ways(3) = Ways(3) + Ways(2) = 3 + 2 = 5
---

From the above examples, we can generalize this recursive pattern as follows :

`Ways(n) = Ways(n-1) + Ways(n-2)`

This equation is similar to Fibonacci numbers except the base values are different. One possible implementation of the above equation is shown below where we call the fib function recursively.

```
function fib(n) {
if (n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
}
```

Watch the following video to understand this puzzle with more examples!