Recursive Functions- Stairs

Question

I have stuck myself in recursive functions and searched some problems online to understand more on how they work. I came through a problem called Staircases and this was the designed code for it-

#include<bits/stdc++.h>

using namespace std;

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

int main(){
    int n;
    cout<<"Enter number of stairs\n";

    cin>>n;

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

    return 0;
}

It would be really helpful if someone could help me understand the staircase function from "int count"{I have understood the base cases} !

Here is a post explaining recursion in great detail https://stackoverflow.com/questions/717725/understanding-recursion — SteveK, Apr 20 '20 at 21:12
`n` becomes smaller and smaller as you pass it in (due to n-1, n-2, and n-3), eventually reaching the base cases of `n == 1` or `n < 0`. This ends the recursion and sums up all numbers moving back up the stack of calls. — SteveK, Apr 20 '20 at 21:16

score 0 · Answer 1 · answered Apr 20 '20 at 21:14

Essentially, this code tries to find how many ways you can get to step n. If you can step either 1, 2, or 3 steps, then you can get to step n from steps n-1, n-2, and n-3. Therefore, the number of ways to get to step n is the sum of the number of ways to get to steps n-1, n-2, and n-3. The code uses recursion to accomplish that, by calling itself 3 times with different step numbers.

StackExchange123 · Answer 2 · 2020-04-20T21:24:26.333

At each function call, you have n stairs left to climb. In one try, you can climb one stair, two stairs or three stairs. So you're calling the function again with n = n - 1 and add its' result to the count. This call stands for the case where you've climbed only one stair (there are n-1 stairs left to climb). Similarly, you add the number of ways you possible after climbing 2 stairs (n = n - 2) and the number of ways possible after climbing 3 stairs (n = n - 3). Note that this function is exponential and it'll take a very long time if n is a big number. You can solve this by using memoization.

#include<bits/stdc++.h>

using namespace std;

const int MAX_SIZE = 100;

long long mem[MAX_SIZE];

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

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

    if (mem[n] != -1)
        return mem[n];

    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 mem[n] = count;
}

int main(){

    for (int i = 0; i < MAX_SIZE; i++)
        mem[i] = -1;

    int n;
    cout<<"Enter number of stairs\n";

    cin>>n;

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

    return 0;
}

Here is the code after using memoization. Note that without memoization, the time it takes to compute will be very long. Try running your code with n = 50 for example, and try it with this code. Also note that even though you can set MAX_SIZE to something like 100,000 , the result will be very big before even n = 100. If you really want to calculate the result for big values of n, you can use what's called "Big Integers".

Recursive Functions- Stairs

2 Answers2