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

Further reading :

• Fibonacci numbers
• Fibonacci numbers puzzles