• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

recursive function call program

 
Ranch Hand
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I cant understand how the out put for the following program comes.

class test{
public static void main(String [] arg){
myMethod(4);
System.out.println("bottom");
}

static void myMethod( int counter)
{
if(counter == 0){
System.out.println("counter ==0");
return;
}
else
{
System.out.println("hello" + counter);
myMethod(--counter);
System.out.println("bye"+counter);
return;
}
}

}


Output:

hello4
hello3
hello2
hello1
counter ==0
bye0
bye1
bye2
bye3
bottom

I can understand how hello part come but how bye parts are coming? I mean when the myMethod is called recursively and when counter=0 then inside if condition there is a return statement which the method terminated know by printing "counter ==0" and finally prints "bottom". so how come bye parts printing?

Thank you.
 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Let's make things simple, first.



You would expect that the output would be:

Because when myMethod() returns, the rest of test() gets executed after the myMethod() call is made.

This is the same principle as the recursion you posted. The path through myMethod(int) gets run, myMethod recursively calls itself, but then has more work to do once that recursive call is done.

Do you see? If not, try writing it on paper to trace the route each method call makes.
 
Ranch Hand
Posts: 1902
Hibernate Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Think about the process as a nesting doll, or like going down into a valley and coming back up on the far side.

Each time it enters myMethod, it proceeds to start the loop with counter having been decremented by one. When it reaches 0, it starts back up through the layers, which goes through the 'bye' printouts for each call of the method. So you should have four printouts of 'hello' and 'bye' respectively.

Bye prints out from 0-3 because the value of counter is printed after it's decremented, before you ask that.

Hope that helps!
 
Ranch Hand
Posts: 281
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
all crazy and beautiful things about STACK's, these are basic concepts of data structures...
 
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have one piece of advice. Don't try and understand recursion, you'll just make yourself crazy.

Anyways, I'm joking. Sort of. I started the following thread in a Usenet newsgroup, comp.programming. You may find it useful, there are some good explanations.

http://groups.google.ca/group/comp.programming/browse_thread/thread/08dcade9abc1bbb5?hl=en&pli=1
 
Author
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

so how come bye parts printing?


Because myMethod() *returns* and continues its execution from where it was called.

I echo the suggestion to run the program "manually" with a paper and pen[cil], paying particular attention to what happens each time myMethod() returns.

Recursion is a fundamental concept in computer science and IMO important to understand. It's not difficult once you understand simple examples like this.
 
Fred Hamilton
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Newton wrote:

so how come bye parts printing?


Because myMethod() *returns* and continues its execution from where it was called.

...



Bingo. Harshana I struggled with the exact same question you did. If you can understand what David has said here, that is the essense of recursion, or a big part of it anyway.

The statements System.out.println("bye"+counter); get executed because of the very reason that David has given. In recursion, a function calls itself, then control is returned to the line after the function call.

 
David Newton
Author
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Seeing it quoted I probably could have said it more clearly, though...

How about:

Because myMethod() resumes execution at the point after it called itself: after the "nested" myMethod() returns the calling myMethod() keeps on going.


Hmm, maybe not ;)

It's just one of those things (like Lisp macros) you have to puzzle out until you hit that "moment of clarity". Stick with it--it's worth it.
 
Fred Hamilton
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Newton wrote:Seeing it quoted I probably could have said it more clearly, though...

How about:

Because myMethod() resumes execution at the point after it called itself: when the "nested" myMethod() returns the calling myMethod() keeps on going.


Hmm, maybe not ;)

It's just one of those things (like Lisp macros) you have to puzzle out until you hit that "moment of clarity". Stick with it--it's worth it.



IMO The first part stands fine by itself. The higlighted part tries too hard. :)

Anyways, I thought the part I quoted in my previous post was clear, consise and to the point. Like you say, you have to take these little "concise statements" and puzzle them out, reach your own understanding or moment of clarity. That's one of the "funny" things about recursion I guess. It's one thing to understand it, it's another thing all together to explain it to someone who doesn't.

p.s. now that I think about it, you might be right, maybe we are leaving something out. My own statement "In recursion, a function calls itself, then control is returned to the line after the function call" leaves something to be desired also. It doesn't address the fact that there is a whole series of return points waiting to be returned to, in the reverse order they were created. In the link I provides, one guy explained it nicely by "unravelling" the recursion and expressing it as an ordered sequence of methods.
 
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Fred Hamilton wrote:Anyways, I'm joking. Sort of.


I would hope so. Although I agree that a simple loop should be preferred where possible*, some data structures (like trees) leave you with little alternatives. So it is good to understand recursion, but it's also good to avoid it if avoiding does not increase complexity too much.

An example where recursion should be avoided (let's ignore StringBuffer.reverse() and StringBuilder.reverse() ):



* If not because it's easier to write and understand, then only to prevent possible StackOverflowErrors
 
Harshana Dias
Ranch Hand
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yo guys..this is the best way to understand recursion...

Think of the programe,

class Test{

public static void main(String [] arg){
printNums(2);
}

static void printNums(int n) {

System.out.println("n"+n);
if( n<0 ) return;
printNums( n - 1 );
System.out.println("n from printNums" +n);

}

}

And the out put is,

n2
n1
n0
n-1
n from printNums 0
n from printNums 1
n from printNums 2


If you cant understand the above output and think of each recursion calls as separate call for different methods.go through the following code..what is the key point of when an method calls(assume a) for a another method(assume b) that calling method (a) wait until the called method (b) return the flow back to calling method (a) and then the rest of the code in calling method (a) get execute.

class Test{

public static void main(String [] arg){
printNums2(2);
}


static void printNums(int n) {
System.out.println("n" + n);
if( n<0 ) return;
printNums( n - 1 );
System.out.println( "n from printNums" + n );
}

static void printNums0(int n ) {
System.out.println("n" + n);
if( n<0 ) return;
printNums( n - 1 );
System.out.println( "n from printNums0 " + n );
}

static void printNums1(int n ) {
System.out.println("n" +n);
if( n<0 ) return;
printNums0( n - 1 );
System.out.println( "n from printNums1 " +n );
}

static void printNums2(int n) {
System.out.println("n"+n);
if( n<0 ) return;
printNums1( n - 1 );
System.out.println( "n from printNums2 " +n );
}

}

output: which comes as the same logic in above recursion programe

n2
n1
n0
n-1
n from printNums0 0
n from printNums1 1
n from printNums2 2


Thank you.
 
David Newton
Author
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Please UseCodeTags.
 
Harshana Dias
Ranch Hand
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Newton wrote:Please UseCodeTags.



Sorry for that..ill use them in future :cool:
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rob Prime: An example where recursion should be avoided (let's ignore StringBuffer.reverse() and StringBuilder.reverse() ):


The only reason that recursion should be avoided in that example is for efficiency reasons. The recursive method is clearer and easier to write. I'd even note that there is an error in the looping version (although the compiler would have let you know about it). My point is that recursion can sometimes be the clearer solution, but low level details about the call stack prevent it from being an optimal solution.

Even in Scala, which has more support for recursion the method has to be "tail recursive" and non-overrideable to see any benefit. Here is an example in Scala which runs in constant stack space. I think it looks a little nicer than the looping method, but not as nice as the naive recursive method.
 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Garrett Rowe wrote:

Rob Prime: An example where recursion should be avoided (let's ignore StringBuffer.reverse() and StringBuilder.reverse() ):


The only reason that recursion should be avoided in that example is for efficiency reasons. The recursive method is clearer and easier to write. I'd even note that there is an error in the looping version (although the compiler would have let you know about it).


Ah yes:

My point is that recursion can sometimes be the clearer solution, but low level details about the call stack prevent it from being an optimal solution.


That's why I said that you should only use recursion if modfying it to a loop would not be too complex. For instance, the following code for traversing a tree (using javax.swing.tree.TreeNode):
Sure, the second piece of code gets the job done, but in this case I would rather shoot myself than use this in production code. It was also a lot harder to write - I actually had to test it to prove it was doing the same.
 
Fred Hamilton
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rob Prime wrote:

Fred Hamilton wrote:Anyways, I'm joking. Sort of.


I would hope so.



Of course it was meant as humor. I can see that the point of the joke might have been lost though. It was a commentary directed at the way one might try to understand more complex recursions, and I probably didn't make it very clear just what I meant. Anyways, it's not really worth explaining.
reply
    Bookmark Topic Watch Topic
  • New Topic