Issue with recursion - I don't understand why I get a reverse output

Question

I'm currently learning recursion in Java. I have made a little code for practice.

public class Tester{
    public static void main(String[] args){
        rec(5);
    }
    public static void rec(int x){
        if(x<=0){
            return;
        }else{
            System.out.print(x+" ");
            rec(x-1);
        }
    }
}
// Output: 5 4 3 2 1

But if I now switch System.out.print(x+" "); with rec(x-1);, I get a completely different output, namely the reverse: 1 2 3 4 5

How can this be possible? I understand it like that:

We have the integer 5 and we go through the method. The if-statement does not apply, so we decrease 5 by 1 and we have x=4, we repeat the method (the print is not reached and thus nothing is printed). As said, we do the same with x=4. If statement does not apply, we decrease 4 by 1 and repeat the method. We repeat till we have that x=0. In this case, we return, so this is the end of the method. I don't understand at all how we have the reverse output, I don't even understand why we have an output...? :s

Ohh...sorry, I didn't read the previous line. The solution is recursion works due to stacks! When you call a recursive function, the current state of your function is stored in the stack. When the function returns, the current state is restored and remaining part is executed. — kiner_shah, Apr 23 '17 at 14:14

score 2 · Answer 1 · answered Apr 23 '17 at 14:15

Try this:

public class Tester{
    public static void main(String[] args){
        rec(5);
    }
    public static void rec(int x){
        if(x<=0){
            return;
        }else{
            rec(x-1);
            System.out.print(x+" ");
        }
    }
}

The reason is that you first need to reach the escape condition (x==0) and then start printing the numbers in the reverse mode compared to your method calling:

rec(5)
    rec(4)
        rec(3)
            rec(2)
                rec(1)
                    rec(0) // We stop here
                System.out.print('1 ')
            System.out.print('2 ')
        System.out.print('3 ')
    System.out.print('4 ')
System.out.print('5 ')

score 1 · Accepted Answer · answered Apr 23 '17 at 14:23

Ok so let us study the first case

First the print statement and then the recursive call: Dry run:

x = 5  Prints 5 then calls rec(4)
x = 4  Prints 4 then calls rec(3)
x = 3  Prints 3 then calls rec(2)
x = 2  Prints 2 then calls rec(1)
x = 1  Prints 1 then calls rec(0)
x = 0  Base case reached, so method returns in the following sequence->
rec(1) -> rec(2) -> rec(3) -> rec(4) -> rec(5) ->main()

Since in this case there was no more statement to be executed after the recursive call, nothing happened and the method started returning back Now for the second case: First the recursive call then the print statement Dry run:

x = 5 as x is not less than equal to 0 goes to rec(4) but print statement is now pending execution. It wont happen until the recursive call returns
x = 4 as x is not less than equal to 0 goes to rec(3) but again print is on hold
x = 3 as x is not less than equal to 0 goes to rec(2) but still print is on hold
x = 2 as x is not less than equal to 0 goes to rec(1) but still print is on hold
x = 1 as x is not less than equal to 0 goes to rec(0) but still print is on hold
x = 0 as x is now 0, rec(0) returns to rec(1)

Now rec(1) had a pending print statment which is now executed with value as 1 then rec(2) had a pending print statement which is now executed with value as 2 then rec(3) had a pending print statement which is now executed with value as 3 then rec(4) had a pending print statement which is now executed with value as 4 then rec(5) had a pending print statement which is now executed with value as 5 and then rec(5) returns to main()

So in this case the output is 1->2->3->4->5 and in the first case it was 5->4->3->2->1

Hope this aids your understanding :-)

score 1 · Answer 3 · edited May 23 '17 at 11:54

The outputs you're getting are correct.

In following case 1:

...
System.out.print(x+" ");
rec(x-1);
...

Correct output is: 5 4 3 2 1

and in following case 2:

...
rec(x-1);
System.out.print(x+" ");
...

Correct output is: 1 2 3 4 5

Explanation: In a recursive function, each call is placed on a stack (hence, executed in last-in-first-out order).

In case 1, the rec(x) first prints the value of its argument and then calls rec(x-1), hence the order happens to be x x-1 x-2 .... Following is the sequence of execution:

rec(5)
    print 5
    rec(4)
        print 4
        rec(3)
            print 3
            rec(2)
                print 2
                rec(1)
                    print 1
                    rec(0)
                        rec(0) return
                    rec(1) return
                rec(2) return
            rec(3) return
         rec(4) return
     rec(5) return

In case 2, the rec(x) function first calls rec(x-1) before printing its argument. Following is the sequence of execution in case 2:

rec(5)
    rec(4)
        rec(3)
            rec(2)
                rec(1)
                    rec(0)
                        rec(0) return
                    print 1
                    rec(1) return
                print 2
                rec(2) return
            print 3
            rec(3) return
         print 4
         rec(4) return
     print 5
     rec(5) return

I hope this helps you to understand the outputs you are getting in aforementioned two cases. I also encourage you to read the following stackoverflow answers here which describe how recursive functions work in more detail.

Oh I think my real issue then is the keyword "return". I have already looked this up on the internet, but its definition is so different and also unclear, I still don't seem to understand its meaning. I always thought it's used to end a method. — cnmesr, Apr 23 '17 at 14:49
@cnmesr: No. I wrote the keyword return in my explanation to tell you the exact sequence of execution. The real issue is printing the number before the recursive call or after the recursive call, this determines the order of output. I don't want to confuse you, but there is an implicit return at the end of every function, even if you don't explicitly write it. — kunal18, Apr 23 '17 at 14:54

Issue with recursion - I don't understand why I get a reverse output

3 Answers3

Linked