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