Recursion program

Question

I am stuck in this code:

Problem. A child can jump the stairs n steps 1,2 or 3 steps at a time. Given the value of n, type all permutations of the order in which it can climb the stairs.

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."); } } 

Conclusion:

  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 result that I get is partly true, partly incomplete. The number of ways to climb the stairs is correct, but as you noticed,

Cleared 2
Reached 3

part of the output goes, as without

Climmed 1
Reached 1

the part before which. I drew a recursion tree, and the tree even suggests that the first part does not exist in the output.

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

Answer 1

Your problem - if I understood the question correctly - is that, for example, if you look at the possibilities that start from climbing from step 0 to step 1, you simply print “climbed from 0 to 1” once and then display all the possibilities, starting from step 1. (Of which, in general, there will be many.)

Instead, you need to arrange that as you go through the recursion, you track the full route, and then when you reach the top of the stairs, you print the entire route.

You could do this, for example, by providing the HoppingLad class HoppingLad array that at the beginning of the call to hop(n,k) describes how the guy reached step k . Then, in the case of n==present you can scan this array to get a complete description of how the guy got from 0 to n .

There are several different ways to organize this, and the problem looks more like homework, so I don't want to fill in too many details. Hope this was helpful despite this.

Answer 2

You print the solution as partial results, so they are not repeated when you get a new solution based on this 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 will return to state 2 (further solutions are not possible) and return to state 1, and then you

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

without printing "1", which allowed you to go to state 1

The decision will list the steps required to transition to the actual state, and when the solution is reached, print the entire list. Of course, since you will use an array or list for this, you will need to remove these steps when you return to previous states.

UPDATE. An alternative (based on changing the output) can be a tabulation of the answer based on the number of steps needed. Ie, the output will be something like this (for the same solution as above):

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

This will allow the user to rebuild the path themselves. Then you will need a new parameter to find out the current number of steps.

If you need an array / list version but don’t want to delete items, you can clone the list and pass a copy to the next function call, but that would be inefficient.

Answer 3

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

What you can do is maintain the String and continue to coordinate the current step, and when the condition is reached, print the entire String , do not print the individual steps. Thus, you will reduce the overhead when checking at each recursive stage how close you are to the solution. You will be sure that 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 above, print "111")

In such problems (usually), where you need to perform a series of steps to reach a threshold value, the most effective solution (usually) is to save a list of steps and then print the entire solution, rather than print individual steps. What you know, you can be sure that all solutions will be covered, and you do not print when the current step does not lead to a solution.

Answer 4

So here is my solution, it uses javascript, although it uses ES6 (for distribution using array parameters, by default, this will work fine in current versions of Firefox, I did it 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:

Possible transition path: 1 1 1

Possible transition path: 1 2

Possible transition path: 2 1

Possible transition path: 3

Common ways to climb 3 steps with an accuracy of 3 jumps at a time: 4

4

The reason I provided a complete solution, unlike Gareth above

This problem looks like homework-y and for this reason I want to share it. Homework is designed to open new horizons. Therefore, sometimes, when I do not have a solution, I continue to force it with my “current skill / mentality”, which will never be able to get me. In the end, when I see the solution and work in the reverse order, he simply added a new facet to my “skill / mentality”. That's why I hate to see solutions say: "I will not fill in too many details because it seems to be homework-y." Since this leads to the only teaching method - the wrong solution to the problem, and then our stupid classification system gives us a bad class, and then "learn from our mistakes." I hate learning from mistakes if this can be avoided. I also probably will not be classified in the Wrong / F caste as a class, especially if I do my best. And it’s not always necessarily true that we learn from “mistakes”, especially when you were simply discarded by our rating system as “failure” / “wrong”.