Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Strange recursive method call! ???

 
Bob Graffagnino
Ranch Hand
Posts: 81
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The output of this program is baffling me! Can anyone explain the output?

This outputs:
myMethod() 0
myMethod() 1
myMethod() 2
myMethod() 3
myMethod() 3
myMethod() 2
myMethod() 3
myMethod() 3
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Bob Graffagnino:
The output of this program is baffling me! Can anyone explain the output?

This outputs:
myMethod() 0
myMethod() 1
myMethod() 2
myMethod() 3
myMethod() 3
myMethod() 2
myMethod() 3
myMethod() 3

Nothing aids understanding recursion like a piece of paper and a pencil. Let me try with a computer and a keyboard.
First, we call myMethod (we'll call this activation 1) with a value of 0.
Activation 1 prints: myMethod() 0. It then goes into the for loop and increments i to 1. It then calls myMethod() with a value of 1 (We'll call this activation 2).
Activation 2 prints myMethod() 1. Process coninutes creating activation 3 and 4 and printing out the next two lines.
In activation 4, i is now 3. The line myMethod() 3 is printed, but the for loop fails on the first try. Now, we can go back to activation 3.
When we left activation 3, i was 3. Execution picks up after the recursive call to myMethod() so we'll test the for loop again. The test fails and this activation of myMethod() completes.
Now, we're back to activation 2, where i is 2. Once again, execution picks up after the recursive call to myMethod(), so we test the for loop. The test succeeds and a new activation (activation 3a) is created with i = 3.
Activation 3a prints myMethod() 3 and then terminates, going back to activation 2. Activation 2 terminates and goes back to activation 1, where i is 1. The process continues until finally, in activation 1, i = 3 and execution completes.
When you're dealing with recursion, draw an activation record stack and follow the flow. It makes life much easier. I sure wish I had a pencil and could draw it for you here.
I hope this clears things up a bit,
Corey
 
Valentin Crettaz
Gold Digger
Sheriff
Posts: 7610
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The key here is the value of i which is passed on to myMethod().
At the first invocation i is 0.
For this method invocation there are gonna be 3 recursion.
i is then incremented and the recursive invocation happens with i=1. So for this methos invocation there are gonna be 2 recursive invocation.
i is incremented again and is now 2, so only one recursion for that invocation.
Finally, is is incremented to 3 and there are no more possible invocation since 3<3 is false.
Basically, the output is to be seen that way:
myMethod() 0 //first invocation
myMethod() 1 //first recursion
myMethod() 2 //second recursion
myMethod() 3 //third recursion (ends here, no more recursion)
myMethod() 3 //second recursion (ends here, no more recursion)
myMethod() 2 //first recursion
myMethod() 3 //first recursion (ends here, no more recursion)
myMethod() 3 //first invocation (end here)
I don't know if this is clear enough, but think of if as if everytime you invoke a method recursively a new execution frame is stacked up the previous one. When the frame is over it is popped out the stack and the previous recursion continues. And so on...
 
Bob Graffagnino
Ranch Hand
Posts: 81
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks. I was forgetting that the method was taking a copy of i.
Geez!
 
chafule razgul
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
I just found out i need more practice on this aspect of the exam... Where can i find similar questions to this one?

TIA
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by chafule razgul:
Hi,
I just found out i need more practice on this aspect of the exam... Where can i find similar questions to this one?

TIA

Here, chafule, I've come up with a quick practice one for you.
What happens when you try to compile and run the following code snippet?

A. The code does not compile because you can not overload the static method printHead.
B. The code does not compile because there is no method printHead which takes an array of Integer objects.
C. The code compiles correctly but performs an infinite loop because of the recursive call in printHead(Object[] list).
D. The code compiles correctly and prints: 1, 2, 3,
E. The code compiles correctly and prints: 1, 2, 3, 1, 2, 3

Come up with an answer and I'll post the solution a little later today, along with an explanation.
I hope this helps you out,
Corey
 
Corey McGlone
Ranch Hand
Posts: 3271
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay - here's the answer and explanation. If you haven't answered the above question yet, don't read this post yet. Once you think you've got the answer, read on.

Answer: D
A is incorrect. You can overload a static method and it is done properly here.
B is incorrect because the method toArray() of the List interface returns an array of Objects, not Integers. If you want to treat an object within the array as an Integer, you must do a cast.
C is not correct - see the explanation in D.
D is correct. When the method printHead is called with the parameter type List, each element is removed from the front of the list and printed. Then, the method is called again with what remains of the list as a parameter. This continues until every element of the list has been removed and printed. When printHead is called a second time, however, the list l is empty, so printHead returns after the first if test. Therefore, the result is "1, 2, 3,".
E is incorrect. See the explanation for D. Had the two calls to printHead been swicthed in order, E would have been correct.
Questions? Comments? Complaints?
I hope this example helps you prepare a little bit.
Corey
 
chafule razgul
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I chose D.. although i did look up the API to see what toArray() returns
Thank you Corey for posting this, i find this quite challenging for my caliber..
After drawing the first question on paper several times over, i finally got it. Thanks javaranch!
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic