Why is recursion giving unexpected results

[shivajikobardan]

Code: [Select]

package com.example.demo;

public class Testy {
    public static void main(String[] args) {
        xMethod(5);
    }

    public static void xMethod(int n) {
        if (n > 0) {
            xMethod(n - 1);
            System.out.println(n + " ");
        }
    }
}

This is the code. I supposed that this should be printing

4,3,2,1,0

Because:

Code: [Select]

package com.example.demo;

public class Testy {
    public static void main(String[] args) {
        xMethod(5);
    }

    public static void xMethod(int n) {
        if (n > 0) {
            System.out.println(n + " ");
            xMethod(n - 1);
        }
    }
}

The above code was printing 5,4,3,2,1 and my guess was correct.

I thought first n=5, then print 5 then n=4

Then n=4, print 4 then n=3

then n=3 print 3 then n=2 and so on...

On that basis I constructed logic for the first program.
But it is printing 1,2,3,4,5. Which baffled me.

This means I do not UNDERSTAND recursion after studying programming basics for 1000 hours(in 2 years). It is embarrassing at this point. However I am not really trying to enter programming software industry so that is fair to the industry.

Please provide some pointers for me.

[tggzzz]

Do you understand how function calls use the stack? Try walking through your code on paper, keeping track of the function arguments pushed on the stack.

Look at the compiler output (use zero optimisation for simplicity).

Single step through your code in the debugger.

[kite31]

As a general advice for understanding recursion, walk through the loop exactly once. If it works then, it should work on repetition.

The difference is that you call xMethod() before printing rather than after. Recursion stacks the calls until it has hit its full depth, then pops the returns to undertake the next action which produces a series of println statements. At the greatest depth, n == 1, pop the next and it is 2, and so on.

In the first example you print before calling.

[shivajikobardan]

I can naively guess that it is a call stack that is being used. And it is just popping the value from the top of the stack that was pushed earlier. But I am not exactly sure of the architecture of data structure that is being used and methodologies that are being followed at code and hardware level. As a CS enthusiast, it is my basic need to understand this. Hope to get some in-depth complete insights here.

[brucehoult]

Recursion is EXTREMELY SIMPLE to reason about. Much easier than loops!

Code: [Select]

    public static void xMethod(int n) {
        if (n > 0) {
            xMethod(n - 1);
            System.out.println(n + " ");
        }
    }

xMethod(5) means ...

- if n > 0 (it is) THEN print the results of xMethod(4) AND THEN print 5 and a space.

Clearly it prints "iii5 ". It can't possibly do anything else than print 5 last.

What is the iii? It is xMethod(4), which is "jjj4 ".

What is the jjj? It is xMethod(3), which is "kkk3 ".

What is the kkk? It is xMethod(2), which is "lll2 "

What is the lll? It is xMethod(1), which is "1 "

[tggzzz]

I can naively guess that it is a call stack that is being used. And it is just popping the value from the top of the stack that was pushed earlier. But I am not exactly sure of the architecture of data structure that is being used and methodologies that are being followed at code and hardware level. As a CS enthusiast, it is my basic need to understand this. Hope to get some in-depth complete insights here.

You already know the search terms necessary to find the answers you want. Use them.

People here are unlikely to want to spend their precious time poorly duplicating information that is widely available. (BTW, ignore hardware; this is purely software)

[golden_labels]

You may approach this by imagining how the machine implements this.⁽¹⁾ But this is an abstract problem and the effect of this code can be evaluated as any other mathematical expression. It’s a plain function composition.

Using pseudocode:

Code: [Select]

n = 2
IF n > 0:
    CALL WITH n - 1
    PRINT n
→

Code: [Select]

IF 2 > 0:
    #######################
    IF 2 - 1 > 0:
        ###########################
        IF 2 - 1 - 1 > 0:
            CALL WITH 2 - 1 - 1 - 1
            PRINT 2 - 1 - 1
        ###########################
        PRINT 2 - 1
    #######################
    PRINT 2

While posting programming questions, tell which language do you use. It doesn’t matter if readers can guess that, or if in your opinion it matters or not. Just make it clear.

⁽¹⁾ Which in fact will be invalid, as the stack is not going to be used in the second case if even most rudimentary optimization is applied.

[shivajikobardan]

I researched a bit further and thus I will rewrite my question further more clearly so that people can understand where my concern is.

# Title: Recursive function and call stack: Basic to Advanced understanding required!

I was solving this particular problem from the textbook in the journey of self-learning.

Trace and Find the output.

    package com.example.demo;
   
    public class Testy {
        public static void main(String[] args) {
            xMethod(5);
        }
   
        public static void xMethod(int n) {
            if (n > 0) {
                System.out.println(n + " ");
                xMethod(n - 1);
            }
        }
    }
   

This was insanely easy for me to grasp. First I will print 5 then call xMethod(4).

Next time, I will then print 4 then call xMethod(3)

And so on.

The output will be 5,4,3,2,1.


The previous question was twisted by a bit. Like this:

    package com.example.demo;
   
    public class Testy {
        public static void main(String[] args) {
            xMethod(5);
        }
   
        public static void xMethod(int n) {
            if (n > 0) {
                xMethod(n - 1);
                System.out.println(n + " ");
            }
        }
    }

I thought OK Fine. I will now just decrement n before printing, that is all. And got 4,3,2,1,0 as my expected hand traced output. Poor me, I was very wrong.

The output is 1,2,3,4,5.

Based on the solution, I can (obviously) see a stack is being used.

I do not see a reason why the print function should execute in the second case.

Once we call xMethod(1)  then We will call xMethod(0). Now in next iteration we are at base case as n no more is greater than zero.
Since nothing is specified for base case, I assume it will simply return (return what i do not know maybe that is the source of the entire confusion) back.
We have started popping now the if(n>0) should no more execute. Hence, print function should no more execute. This is my concern.

I hope I am clear.


# Edit 2


Based on further research, it seems to be that once xMethod(0) is executed, we execute print function.


Let's say xMethod(0) returns to xMethod(1) Nothing. But the return should be happening all at once (without executing the print function is what I feel). So, x(1) returns nothing to x(2).......and so on till x(4) returns nothing to x(5). Finally the print function should be executed. But if that is the case, how will the n values be stored? Because stack has already been popped by now. How will the program remember the values that were already popped from stack?


This leads me to believe the most possible thing. Popping and printing happens one after another instead. But why? I do not understand that. I am not seeking some deep level stuff, but simple logic and understanding is fine.

[kite31]

It seems to me that excellent advice has been given by various other people, yet I will try one more time to help you understand the difference between calling xMethod() after or before the print.

You stand at the top of a staircase with three steps. In version 1, you print your number then take a step down while reducing the number. Print comes before xMethod(). Repeat until you reach the bottom step. There is nothing left to do so you return to the stop step with no further actions in the code. The numbers are 3 2 1

In version 2 you take a step down while reducing the number, then another step while reducing the number, then another to the bottom. At no time have you yet reached a print instruction, only xMethod which took you to the next step. Now you face a series of print instructions as you step back up but, being at the bottom, your first print is the 1 you are holding. Going up to the top you have 1 2 3.

As mentioned, there are great resources out there. Given you are still asking here, maybe this will help.

[golden_labels]

shivajikobardan, don’t try to do it in your mind. Use pen and paper (most convenient) or write it in some text editor.

While reporting back, tell us what you did. If you just repeat, that you don’t understand, we don’t know your thinking process. And if we don’t know your thinking process, we can’t correct it.

You wrote how function calls terminate. Yes, this is correct. But it doesn’t say anything about printing in relation to the calls. And this is the crucial part here.

In my earlier explanation I show the final, expanded result. You just follow the second code snippet. It literally shows in what order prints are done. It’s linear code with no recursion or loops, and conditionals are left only for clarity and determine nothing.

Yet another option is using the normal method with tabulating variable values. You just need to add more columns for recursive calls. And perhaps recursion depth to keep track of it.

[sleemanj]

I think your confusion might be that you don't understand two things

   1. Function calls are encapsulated, what happens in them, doesn't affect what happens out of them (iognoring globals, I/O etc), even if it's a recursive call.
   2. When a function ends, either by explicit return, or an implicit, then it returns controil back to the point at which the function was called.


Your example `xMethod(5);` with

Code: [Select]

    public static void xMethod(int n) {
        if (n > 0) {       
            xMethod(n - 1);
            System.out.println(n + " ");
        }
    }

Performs the following steps

Code: [Select]

  1. Call xMethod(5);  making n1 = 5
    1. Because n1 > 0, call xMethod(n1 - 1); making n2 = 4
      1. Because n2 > 0, call xMethod(n2 - 1); making n3 = 3
        1. Because n3 > 0, call xMethod(n3 - 1); making n4 = 2
          1. Because n4 > 0, call xMethod(n4 - 1); making n5 = 1
            1. Because n5 > 0, call xMethod(n5 - 1); making n6 = 0
              1. Because n6 == 0, return
            2. Print n5 + " " ("1 ") and return
          2. Print n4 + " " ("2 ") and return
        2. Print n3 + " " ("3 ") and return
      2. Print n2 + " " ("4 ") and return
    2. Print n1 + " " ("5 ") and return
  2. End


[radiolistener]

Code: [Select]

package com.example.demo;

public class Testy {
    public static void main(String[] args) {
        xMethod(5);
    }

    public static void xMethod(int n) {
        if (n > 0) {
            xMethod(n - 1);
            System.out.println(n + " ");
        }
    }
}

This is the code. I supposed that this should be printing

4,3,2,1,0

There are 3 mistakes in your code:

1) You call xMethod first and println second. It is important to invoke methods in the order you want them executed. In your case, xMethod is called first and it calls itself recursively. As a result, execution reaches the deepest recursive call before println is executed. Only as the recursion unwinds does control return to the original call, causing println to execute last in the first call and first in the deepest call.

2) You expect the output 4, 3, 2, 1, 0, but you call xMethod from main with the value 5 instead of 4.

3) In xMethod, you check if (n > 0), so only values greater than 0 are printed. Since you expect 0 to be included, the condition should be if (n >= 0).

Here is the corrected code with these issues fixed:

Code: [Select]

public class test {
    public static void main(String[] args) {
        xMethod(4);                         // use 4 to start from 4
    }

    public static void xMethod(int n) {
        if (n >= 0) {                       // use n >= 0 to include value 0
            System.out.println(n + " ");    // first call to println
            xMethod(n - 1);                 // second enter into recursion
        }
    }
}


[brucehoult]

There are 3 mistakes in your code:

These are not mistakes. It is example code to be analysed and understood.

Recursive calls can legitimately be the first action a function takes, the last action, or something in the middle -- possibly multiple times/places.

And I believe advice to simulate it, think about stacks etc, is misguided. The point of recursion is that it permits -- encourages -- STATIC analysis of one execution of a function in isolation, assuming that other functions correctly do their job, as defined by their specification. For this, it is irrelevant whether those calls are of other functions (e.g. printf()) or recursive calls of the same function.

The specification of the function in question is "Print whole numbers from 1 to n, inclusive, in that order, with each number followed by a space character.

You function implements a different specification: printing numbers in descending order.

[radiolistener]

The specification of the function in question is "Print whole numbers from 1 to n, inclusive, in that order, with each number followed by a space character.

You function implements a different specification: printing numbers in descending order.

As I understand the original poster’s message, his intention was actually to implement the function so that it prints the numbers in descending order. He even wrote:

This is the code. I supposed that this should be printing

4,3,2,1,0

However, the implementation he ended up with matches the specification you mentioned - printing whole numbers from 1 to n in ascending order:

On that basis I constructed logic for the first program.
But it is printing 1,2,3,4,5. Which baffled me.

which is why he was confused by the result.

The main mistake of the original poster is actually quite simple: he just calls println and xMethod in the wrong order. For some reason, nobody noticed this initially, and the discussion shifted to recursion details, yet the core error was never clearly explained to him.

In short, the original poster intended to write code that prints 4,3,2,1,0. However, his code does not behave as expected and instead outputs 5,4,3,2,1. He is unable to understand why. Above, I have outlined three mistakes in his code that cause it to behave differently from what he intended.

Perhaps I misunderstood something, but that is how I read his message... 

[shivajikobardan]

brucehoult is correct. It is purposely given like that for us to analyze and learn.

[golden_labels]

The specification of the function in question is "Print whole numbers from 1 to n, inclusive, in that order, with each number followed by a space character.

You function implements a different specification: printing numbers in descending order.

No, and it is clear: they provided a snippet that does exactly what you consider to be the question. Why would they post the correct answer and then ask, how to write it? (This is a rhetorical question, you are expected to not reply to that)

brucehoult is correct. It is purposely given like that for us to analyze and learn.

And what is the progress with analyzing and learning? You still didn’t give us anything, which could be used to help you.

[magic]

I think your confusion might be that you don't understand two things

   1. Function calls are encapsulated, what happens in them, doesn't affect what happens out of them (iognoring globals, I/O etc), even if it's a recursive call.
   2. When a function ends, either by explicit return, or an implicit, then it returns controil back to the point at which the function was called.

Basically this. You need to understand that the n which equals 5 when xMethod() is initially called by main() is separate from the n which equals 4 when xMethod() calls itself.

So the meaning of xMethod() is:

if (n > 0) {
    make a copy of n, decrement it by 1, run xMethod() recursively on the decremented copy of n
    after recursive xMethod() completes execution:
    print the original value of n
} else {
    do nothing and return immediately, allowing earlier xMethod() to continue
}

This obviously prints 1 2 3 4 5.

[radiolistener]

No, and it is clear: they provided a snippet that does exactly what you consider to be the question. Why would they post the correct answer and then ask, how to write it?

However, the original poster did not mention any of that in original post. In his first message, he clearly stated that he wrote the initial code expecting it to produce 4,3,2,1,0, but it actually outputs 1,2,3,4,5, and he couldn’t understand why. That is all I saw, so I didn’t try to speculate about what task he was given or what his teachers intended. I simply explained why the code he wrote produces a different result from what he expected and how to fix it to get 4,3,2,1,0, as he intended. He didn’t ask about anything else in his first message.

[TheCalligrapher]

This is the code. I supposed that this should be printing

4,3,2,1,0

Um... Your question sounds like "why 2+2 is 4 when I expected it to be 11?" Questions like that are impossible to answer without additional clarifications, since in the original form they simply make no sense.

First and foremost, you have to explain to us why you expected this code to output "4,3,2,1,0"? Why, really? And what puzzles me most is why you expected this sequence to start with 4, when the top-level call in your code is clearly given 5 as an argument. Also, why did you expect to see 0 in the output when the `if` in your code is clearly crafted to prevent this from happening?

[kite31]

... why you expected this sequence to start with 4, when the top-level call in your code is clearly given 5 as an argument. Also, why did you expect to see 0 in the output when the `if` in your code is clearly crafted to prevent this from happening?

Straightforwardly, shivajikobardan expected the println which is subsequent to the recursive call to be executed at once despite the method call prior. Thus, 4,3,2,1,0 makes sense as an output, provided only that 2+2 = 11

After all of these contributions, I should hope he or she has grasped that by now. Some feedback would be nice.

[ledtester]

First and foremost, you have to explain to us why you expected this code to output "4,3,2,1,0"?

I think this would have been a good way to direct the conversation - the crux of the problem might have gotten to much more quickly.

[brucehoult]

The main mistake of the original poster is actually quite simple: he just calls println and xMethod in the wrong order. For some reason, nobody noticed this initially, and the discussion shifted to recursion details, yet the core error was never clearly explained to him.

What do you mean "no one noticed". Everyone noticed, including OP. The original message included two versions copies of the code with both orders. OP, and everyone else, completely understood that there were two orders of those two statements. OP was simply confused about why the two orders produced different results.

[IanB]

The OP was (and probably still is) simply confused. There is no need for any qualification.

I mean, just consider a fundamental thing:

Code: [Select]

        if (n > 0) {
            xMethod(n - 1);
            System.out.println(n + " ");
        }


This is the code. I supposed that this should be printing

4,3,2,1,0

Given the test for n > 0, there is no way for the code ever to print a value of "0".

[kite31]

The OP was (and probably still is) simply confused. There is no need for any qualification.

I mean, just consider a fundamental thing:

Code: [Select]

        if (n > 0) {
            xMethod(n - 1);
            System.out.println(n + " ");
        }


This is the code. I supposed that this should be printing

4,3,2,1,0

Given the test for n > 0, there is no way for the code ever to print a value of "0".

There is if the OP imagines that the println statement is [mysteriously] executed within the same sequence as the xMethod call, without xMethod being called first.

That in fact appears to have been their fundamental error. Walk through the code as if xMethod did not divert execution from the subsequent println until after println executed.

I know it makes no sense to us, but the OP thought execution would be:

Code: [Select]

decrement n
(defer call to xMethod)
print n
now execute the xMethod callas if the entirety of the method executed and only then did the earlier recursive call actually happen.

Edit: attempt to clarify

[shivajikobardan]

Thank you all I seem to have get it.