Q:

# Stair Case: C++ program to solve the staircase problem

A child is running up a staircase with N steps, and can hop 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up to the stairs? You need to return number of possible ways W.

Input format: Line 1: Integer N (No. of steps)

Output Format: Line 1: Integer W i.e. Number of possible ways

Constraint: (1 <= N <= 30)

Sample Input 1: 4

Sample Output: 7

Explanation:

In this question, to find out the number of ways to we can climb the stairs, we can use a recursive method to solve it. We can call the recursive function thrice in our code with parameters of (N-1)(N-2) and (N-3) steps (the decrease in steps show the number of steps climbed). And add and return them.

It is one of the typical questions for recursive algorithms.

Algorithm:

1. Step 1: Declare a recursive function staircase with one parameter (int steps).
2. Step 2: Base Case:
if(steps <0) // No steps to climb
return 0;
3. Step 3: Base Case 2:
return 1;
4. Step 4: Return staircase (steps -1) + staircase (steps – 2) + staircase (steps -3).
i.e. the total ways in which we can climb the steps.

Example:

```    For stairs = 3.
Ways to climb are,
1 1 1
1 2
2 1
3
Hence there are four ways to climb.```

C++ program:

``````#include<bits/stdc++.h>

using namespace std;

//Recursive Function
int staircase(int n){
if(n<0){            //Base Case 1
return 0;
}

if(n==0){           //Base Case 2
return 1;
}

int count = 0;
count += staircase(n-1);    //Stepping 1 step
count += staircase(n-2);    //Stepping 2 step
count += staircase(n-3);    //Stepping 3 step

return count;
}

//Main
int main(){
int n;
cout<<"Enter number of stairs"<<endl;
cin>>n;

cout<<"No of ways to climb stairs are ";
cout<<staircase(n)<<endl;

return 0;

}``````

Output

```Enter number of stairs
5
No of ways to climb stairs are 13
```