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:
if(steps <0) // No steps to climb
return 0;
if(steps ==0) //Already reached top
return 1;
i.e. the total ways in which we can climb the steps.
Example:
C++ program:
Output