7

Ladder Problem Using Recursion - A Complete Guide - JournalDev

 2 years ago
source link: https://www.journaldev.com/59494/ladder-problem-using-recursion-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

In today’s article, we will discuss and solve the ladder problem using recursion. It is a very popular problem for interview preparation as well. We will first go through the problem statement and later look at the algorithm. So, without wasting any time, let’s get started.

Problem Statement

Jack wants to climb up a ladder that is N steps long. At each step, Jack can take a jump up to 3 steps. Determine the total number of ways in which Jack can reach the top of the ladder.

Concept of the Ladder Problem

The problem is very simple if one can visualize what’s going on. Imagine that you are Jack and try to approach this problem. Suppose you are at step N – think of the ways by which you could’ve reached there.

As Jack can only jump a maximum of 3 steps at a time, how can we use this information to reach the Nth step?

If you tried to imagine the situation, great job! There can be multiple ways to solve the same problem, and below is the one which I would use.

If I am standing at the Nth step, then I have only 3 ways to reach there.

  1. By taking a jump of 1 step from the (N – 1)th step.
  2. Or by taking a jump of 2 steps from the (N – 2)th step.
  3. Otherwise, I am left with only one way, to use the (N – 3)th step and take a jump of 3 steps.

Well, you might be thinking, how would that lead to a solution? Just wait and watch, you’ll get the answer to all your doubts. The approach that I used above gives us a recursive mathematical relation.

Recursive Relation: f(N) = f(N - 1) + f(N - 2) + f(N - 3)

Note: The above relation transforms to the following relation if the allowed steps are stored in a vector of M elements.

Recursive Relation: f(N) = f(N - A1) + f(N - A2) + f(N - A3) + ...... + f(N - Am)

Base case will be N = 0.

Example 4Example

Pseudocode to solve the Ladder Problem

ways(N, steps)
// check for base cases
if N == 0
return 1
// otherwise
ans <-- 0
// iterate over all the step sizes
for i = 0 to i = size(steps) - 1
jump_size <-- steps[i]
if(N - jump_size >= 0)
ans <-- ans + ways(N - jump_size, steps) // recursion
return ans

Ladder Problem Using Recursion in C++

Now let’s get right into the code and solve the ladder problem using recursion in C++.

#include <iostream>
#include <vector>
using namespace std;
int ways(int N, vector <int> steps)
{
// base case
// for N == 0, the only way
// is to stay there only
if(N == 0)
return 1;
// otherwise, initialize the answer
// with 0
int ans = 0;
// now iterate over the steps vector
// we will try to use every possible
// jump size
for(int i = 0; i < steps.size(); i++)
// if N - jump size >= 0
// we can use this step
if(N - steps[i] >= 0)
ans += ways(N - steps[i], steps);
return ans;
}
int main()
{
cout << "Enter the value of N" << endl;
int N;
cin >> N;
cout << "Enter the values of allowed steps, press -1 to stop" << endl;
vector <int> steps;
while(true)
{
int ele;
cin >> ele;
if(ele == -1)
break;
steps.push_back(ele);
}
cout << "Total Number of steps to reach the topmost step: " << ways(N, steps) << endl;
return 0;
}
Recursive Algorithm Ladder ProblemRecursive Algorithm Ladder Problem

Output

Image 7Image 7

Conclusion

In this article, we learned to solve the ladder problem using the recursive approach. Though the recursive algorithm is not optimal, we still understood the concept lying behind this particular problem. Recursive problems are more of imagination and visualization problems. One must think to approach these problems by considering proper and necessary base cases. That’s all for today, thanks for reading.

Further Reading

If you want to learn more about recursion, do check out the following articles

https://www.journaldev.com/56866/solving-0-n-knapsack-problem-in-cpp

https://www.journaldev.com/58606/fibonacci-series-using-dynamic-programming-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK