Consider the following problem: A person is about to climb a staircase of n stai
ID: 3877109 • Letter: C
Question
Consider the following problem: A person is about to climb a staircase of n
stairs. Each step she makes can be either a regular-size step that climbs 1 stair, or a big-size step
that climbs 2 stairs. In how many di erent ways can she climb the whole set of n steps ? E.g., for
climbing 3 stairs she has 3 possible ways: (reg,reg,reg), (reg,big), (big,reg). Note you don't need to
explicitly write her steps but only the number of options she has.
Write a recursive solution for solving the problem.
Hint: Think about the base cases ; then look at her last step to de ne the smaller instances and
transition: it is either reg or big. If it is reg, then she rst has to get to stair n-1; if it is big, she
rst needs to get to stair n-2. Does it seam familiar ?
Explanation / Answer
Solution:
when n = 1 , ways = 1 (reg)
when n = 2, ways = 2 (reg,reg) or (big)
when n = 3, ways = 3
when n = 4, ways = 5
So, this is following fibonacci series with starting values as 1 and 2.
From the hint if we think,
1. To reach stair n - we can reach from stair n-1 or stair n-2.
2. So total possible ways to reach stair n, are totalWays(n-2) + totalWays(n-1)
So, recursive solution is as follows:
procedure totalWays(n):
if (n <= 2) then
return n
else
return totalWays(n-1) + totalWays(n-2)
C Code:
#include<stdio.h>
int totalWays(int n)
{
if(n<=2)
return n;
return totalWays(n-1) + totalWays(n-2);
}
int main()
{
printf("Total ways for 4 stairs: %d",totalWays(4));
return 0;
}