Recursion Program

Question

I am stuck up in this code:

Problem: A child can hop a staircase of steps n in 1,2 or 3 steps at one time. Given a value of n, print all the permutations of the order in which he can climb the staircase.

This is my code:

    public class HoppingLad
    {
        int count;
        void hop(int n,int present)
        {
            if(n==present)
            {
                count++;
                System.out.println("\nFinished type "+count+" climbing.\n");
            }
            else
            {
                if((n-present)>=1)
                {
                    System.out.print("\nClimbed 1 step.\nReached "+(present+1)+"   ");
                    hop(n,present+1);
                }
                if((n-present)>=2)
                {
                    System.out.print("\nClimbed 2 step. \nReached "+(present+2)+"   ");
                    hop(n,present+2);
                }
                if((n-present)>=3)
                {
                    System.out.print("\nClimbed 3 step. \nReached "+(present+3)+"   ");
                    hop(n,present+3);
                }


            }

        }

        public static void main(String [] args)
        {
            HoppingLad hl=new HoppingLad();
            hl.hop(3, 0);
            System.out.println("There are "+hl.count+" ways to climb.");
        }
    }

The output is :

 Climbed 1 step.  
 Reached 1  
 Climbed 1 step.  
 Reached 2  
 Climbed 1 step.  
 Reached 3   
 Finished type 1 climbing.


 Climbed 2 step. 
 Reached 3   
 Finished type 2 climbing.


 Climbed 2 step. 
 Reached 2   
 Climbed 1 step.
 Reached 3   
 Finished type 3 climbing.


 Climbed 3 step. 
 Reached 3   
 Finished type 4 climbing.

 There are 4 ways to climb.

The output I get is partly correct, partly incomplete. The number of ways to climb the staircase is correct but as you notice,

Climbed 2
Reached 3

part of the output is coming as it is without

Climbed 1
Reached 1

part coming before it. I have drawn the recursion tree and the tree even suggests that the first part is not there in the output.

However, the user has to be instructed from the ground level. I have tried many things, to no avail. Can anyone fix this out for me please?

Answer 1

So here is my solution, it uses javascript though, it uses ES6 (for spread operating on array, default parameters, this will run fine in current versions of Firefox, I did this in Firefox 50):

function getHopPathsCnt(totalsteps, maxhopability, curstep = 0, taken = [], total={count:0}) {
  if (totalsteps === curstep) {
    total.count++;
    console.log('A possible hop path:', taken.join(' '));
  } else {
    for (let hopped = 1; hopped <= maxhopability; hopped++) {
      if (totalsteps - curstep >= hopped)
        getHopPathsCnt(totalsteps, maxhopability, curstep + hopped, [...taken, hopped], total);
    }
  }
  if (curstep === 0) {
    console.error('Total ways to climb', totalsteps, 'steps with up to', maxhopability, 'hops at a time:', total.count);
    return total.count;
  }
}

To use it:

getHopPathsCnt(3, 3);

Outputs:

A possible hop path: 1 1 1

A possible hop path: 1 2

A possible hop path: 2 1

A possible hop path: 3

Total ways to climb 3 steps with up to 3 hops at a time: 4

4

Reason I provided full solution unlike Gareth above

This problem does look homework-y and for that reason I want to share it. Homework is meant to open up new horizons. So sometimes, when I don't have a solution, I keep forcing it with my "current skill/mentality", which may never get me anywhere. Eventually when I see the solution and work in reverse, it just added a new facet to my "skill/mentality". That's why I hate seeing solutions say "I won't fill in too many details because it seems homework-y". As that leads to the only method of learning being - getting the problem wrong, and then our silly grading system giving us a bad grade, and then "learn from our mistakes". I hate learning from mistakes if it can be avoided. I also rather not be classed into a caste of "Wrong"/"F" as a grade, especially if I put in effort. And its not always necessarily true that we learn from "mistakes", especially when you were just casted by our grading system as a "failure"/"got it wrong".

Answer 2

I have implemented this solution. I will email you only if you have completed your homework.

What you can do is maintain a String and keep concating the current step taken and when the condition is reached, print the entire String, do not print individual steps. That way, you will reduce the overhead of checking at every recursive step how close you are to the solution. You will be sure the path will be printed only if the current step leads to a solution.

For example (suppose n=3)

3,0,"" -> 3,1,"1" -> 3,2,"11" -> 3,3,"111" (one solution over, print "111")

In these kind of problems (generally), where you need to make a series of steps to reach a threshold value, the most efficient solution (generally) is to store the list of steps and then print the entire solution rather than printing individual steps. That whay you know you can be sure you gets all solutions covered, and you are not printing when the current step does not lead to a solution.

Answer 3

You are printing the solution as partial results, so they are not repeated when you get a new solution based in that partial solution.

In other words, you do (for n= 3)

        --> state 0
hop(1)  --> state 1 --> print "1"
hop(1)  --> state 2 --> print "1"
hop(1)  --> state 3 --> print "1" --> print "solution";

then you go back to state 2 (no further solutions possible) and back to state 1, and then you

hop(2) --> state 3 --> print "2" --> print "solution"

without printing the "1" that allowed you to get to the state 1

The solution would be passing the list of steps needed to get to the actual state and, when a solution is reached, print all the list. Of course, since you will use an array or List for this, you will need to delete those steps when you go back to previous states.

UPDATE: An alternative (based in the changing the output) could be tabulating the answer based in the number of steps needed. I.e., the output would be something like that (for the same solution as above):

Climbed 1
          -> Climbed 1
                       -> Climbed 1. Solution Found!
          -> Climbed 2. Solution Found!

That would allow the user to rebuild the path by itself. Then again, you need a new parameter to know the current number of steps.

If you want the array / List version but do not want to delete items, you can clone the list and pass a copy to the next function call, but that would be inefficient.

Answer 4

Your problem -- if I've understood the question correctly -- is that when, e.g., you consider the possibilities that start with climbing from step 0 to step 1, you just print out "climbed from 0 to 1" once and then display all the possibilities starting from step 1. (Of which, in general, there will be lots.)

Instead, you need to arrange that as you go through the recursion you keep track of the complete route, and then when you reach the top of the staircase you print out the whole route.

You could do this, for instance, by giving the HoppingLad class an array that, at the start of an invocation of hop(n,k), describes how the lad got to step k. Then, in the n==present case, you can look through that array to output a complete description of how the lad got from 0 to n.

There are a few different ways to organize this, and the problem looks rather homework-y so I'd rather not fill in too many details. I hope the above is helpful despite this.