recursive function call program

[Harshana Dias]

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.

[Steve Luke]

Let's make things simple, first.

public void test()
{
    System.out.println("Top");
    myMethod();
    System.out.println("Bottom");
}

public void myMethod()
{
    System.out.println("Middle");
    return;
}

You would expect that the output would be:

Top
Middle
Bottom

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.

[Theodore Casser]

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!

[Robin John]

all crazy and beautiful things about STACK's, these are basic concepts of data structures...

[Fred Hamilton]

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

[David Newton]

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]

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]

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]

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.

[Rob Spoor]

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() ):

public String reverseRecursively(String s)
{
    if (s.length() <= 1)
    {
        return s;
    }
    return reverseRecursively(s.substring(1)) + s.substring(0, 1);
}

public String reverseLooping(String s)
{
    if (s.length() == 1)
    {
        // not necessary but a bit more efficient
        return s;
    }
    char[] array = s.toCharArray();
    for (int i = 0; i < array.length / 2; i++)
    {
        char tmp = array[i];
        array[i] = array[array.length - 1 - i];
        array[array.length - 1 - i] = tmp;
    }
}

* If not because it's easier to write and understand, then only to prevent possible StackOverflowErrors

[Harshana Dias]

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]

Please UseCodeTags.

[Harshana Dias]

David Newton wrote:Please UseCodeTags.

Sorry for that..ill use them in future :cool:

[Garrett Rowe]

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.

def reverse(s: String): String {
   def rev(ss: String, acc: String): String {
      if (ss.isEmpty) acc
      else rev(ss.substring(1), rev.charAt(0) + acc)
   }
   rev(s, "")
}

[Rob Spoor]

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:

return new String(array);

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):

public void traverseRecursively(TreeNode node)
{
    // handle node
    for (Enumeration<?> e = node.children(); e.hasMoreElements(); )
    {
        TreeNode child = (TreeNode)e.nextElement();
        traverseRecursively(child);
    }
}

public void traverseLooping(TreeNode node)
{
    // handle node
    Deque<Enumeration><?>> stack = new LinkedList<Enumeration><?>>();
    Enumeration<?> current = node.children();
    stack.addLast(current);
    while (!stack.isEmpty())
    {
        if (current.hasMoreElements())
        {
            TreeNode child = (TreeNode)current.nextElement();
            // handle child
            Enumeration<?> e = child.children();
            if (e.hasMoreElements())
            {
                current = e;
                stack.addLast(e);
            }
            // else skip, continue with current
        }
        else
        {
            // current has been exhausted, stack is not empty
            stack.removeLast();
            if (!stack.isEmpty())
            {
                current = stack.getLast();
            }
        }
    }
}

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]

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.