Ladder Problem Using Recursion – A Complete Guide

Filed Under: C++
Ladder Problem Using Recursion

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 4
Example

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 Problem
Recursive Algorithm Ladder Problem

Output

Image 7
Image 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

close
Generic selectors
Exact matches only
Search in title
Search in content