recursion, what's the difference in the stack?

Question

In the following program what's the difference in the stack execution of each method?

public class Return{
    public static void main(String[] args){
        System.out.println('\u000C');            
        
        rt0(50);        
        rt1(50);
        
    }
   
    public static void rt0(int n){
        
        if(n == 1)return;
        else{ 
            System.out.println(n);
            rt0(n-1);                
        }            
    }
    
    public static int rt1(int n){
        
        if(n == 1)return n;
        else { 
          System.out.println(n);
          return rt1(n-1);
        }            
    }        
}

Could you please clarify what the question here is? Both methods count down from 50 to 2, and `rt1` in the end returns 1. Also why do you have this `println('\u000C')` at the beginning? Is this a question about how the JVM executes this, how the Java byte code for this looks like, if there is tail recursion support, ...? — Marcono1234, Apr 23 '23 at 13:41
The ‘/u000C’ simply clears the screen in the bluej ide. I’m trying to understand the difference between calling a method recursively and returning a method recursively. I understand in the later why you can run out of memory but seems odd you run out when you’re just calling the method. — DCR, Apr 23 '23 at 14:05

score 0 · Answer 1 · answered Apr 23 '23 at 14:31

Not completely sure if that answers your question, but the only difference for method rt0 and rt1 is that one returns a value every time it is called while the other does not.

You can also compare the Java bytecode for them if you want by running javac Return.java and then javap -v Return.class. For JDK 17 I get this output:

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=1, args_size=1
         0: getstatic     #7                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: bipush        12
         5: invokevirtual #13                 // Method java/io/PrintStream.println:(C)V
         8: bipush        50
        10: invokestatic  #19                 // Method rt0:(I)V
        13: bipush        50
        15: invokestatic  #25                 // Method rt1:(I)I
        18: pop
        19: return
      LineNumberTable:
        line 3: 0
        line 5: 8
        line 6: 13
        line 8: 19

  public static void rt0(int);
    descriptor: (I)V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=1, args_size=1
         0: iload_0
         1: iconst_1
         2: if_icmpne     6
         5: return
         6: getstatic     #7                  // Field java/lang/System.out:Ljava/io/PrintStream;
         9: iload_0
        10: invokevirtual #29                 // Method java/io/PrintStream.println:(I)V
        13: iload_0
        14: iconst_1
        15: isub
        16: invokestatic  #19                 // Method rt0:(I)V
        19: return
      LineNumberTable:
        line 12: 0
        line 14: 6
        line 15: 13
        line 17: 19
      StackMapTable: number_of_entries = 1
        frame_type = 6 /* same */

  public static int rt1(int);
    descriptor: (I)I
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=1, args_size=1
         0: iload_0
         1: iconst_1
         2: if_icmpne     7
         5: iload_0
         6: ireturn
         7: getstatic     #7                  // Field java/lang/System.out:Ljava/io/PrintStream;
        10: iload_0
        11: invokevirtual #29                 // Method java/io/PrintStream.println:(I)V
        14: iload_0
        15: iconst_1
        16: isub
        17: invokestatic  #25                 // Method rt1:(I)I
        20: ireturn
      LineNumberTable:
        line 21: 0
        line 23: 7
        line 24: 14
      StackMapTable: number_of_entries = 1
        frame_type = 7 /* same */

If you diff the code for both methods the main difference is that one method does not return a value whereas the other one does:

return
...
return

vs.

iload_0
ireturn
...
ireturn

For neither of them you should run out of memory (java.lang.OutOfMemoryError), at most you might run into a java.lang.StackOverflowError, but only if you drastically increase that number 50 in your sample code, for example to 100000.

The stack overflow is similar to what you would get with many programming languages because each time the method recursively calls itself some memory is needed to store certain information, such as who was calling the method or which local variables are present in the caller. Eventually you will run out of available stack memory which causes the StackOverflowError.

Some other programming languages can avoid the stack overflow for tail-recursive calls, but that is not the case for Java yet, see for example this question.

recursion, what's the difference in the stack?

1 Answers1