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

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:
   if(steps ==0) //Already reached top
   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