Why does this recursion behave this way?

Issue

I'm learning about recursion and I ran this function to track the "count" variable to see how it changes while the recursion is going through. After getting 4 strings of "Hello." back after the count was already 0 I wanted to check what was happening to the count. I found that it was actually incrementing by one, but I don't know why it would. Why is the count incrementing after the count was already set at 0? Is it going back to its original value after terminating the recursion?

public class Main {
    public static void main(String[] args) {
         
        sayHi(4);
    }

    public static void sayHi(int i) {
        int count = i;
        System.out.println(count);
        if(count == 0) return;


        System.out.println("hi!");
        sayHi(count - 1);

        System.out.println(count);

        System.out.println("Hello.");


    }
}

This is the output of the code:

OUTPUT: 

4
hi!
3
hi!
2
hi!
1
hi!
0
1
Hello.
2
Hello.
3
Hello.
4
Hello.

Solution

It's not incrementing, and in fact the value of count never changes at all. It's just being output twice:

int count = i;
System.out.println(count); // <--- first here
if(count == 0) return;

System.out.println("hi!");
sayHi(count - 1);

System.out.println(count); // <--- then here
System.out.println("Hello.");

In between those two is where the recursion occurs. So in the output:

4    // these
hi!  // are
3
hi!
2
hi!
1
hi!
0
1
Hello.
2
Hello.
3
Hello.
4      // the outermost
Hello. // method call

and:

4
hi!
3    // these
hi!  // are
2
hi!
1
hi!
0
1
Hello.
2
Hello.
3      // the second outermost
Hello. // method call
4
Hello.

Until:

4
hi!
3
hi!
2
hi!
1
hi!
0    // this is the innermost method call
1
Hello.
2
Hello.
3
Hello.
4
Hello.

There's nothing special about recursion, and new developers tend to very much over-think it. The method itself doesn't do anything particularly complex. Ignore for a moment that it's recursive and just examine what it does:

int count = i;                // declare a value, which never changes
System.out.println(count);    // output that value
if(count == 0) return;        // conditionally return (the innermost does this)

System.out.println("hi!");    // output a string
sayHi(count - 1);             // call a method, which itself may generate lots of output

System.out.println(count);    // output the same value again
System.out.println("Hello."); // output another string

So, unless the value passed to the method is 0, every call to the method will produce four lines of output:

• the number that was passed to it
• a string
• the number that was passed to it again
• another string

So for any call to the method where you don't pass the value 0, you should expect to see the value that you do pass to it output twice.

Answered By - David