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

Here, we are going to implement a C++ program to solve the staircase problem.
Submitted by Indrajeet Das, on December 14, 2018

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:

Step 1: Declare a recursive function staircase with one parameter (int steps).
Step 2: Base Case:
if(steps <0) // No steps to climb
return 0;
Step 3: Base Case 2:
if(steps ==0) //Already reached top
return 1;
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