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

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