Java Code:
public class SimpleRecursion {
public int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
}
Gives the following bytecode for the factorial method (I executed javap to generate it):
public int factorial(int); descriptor: (I)I flags: ACC_PUBLIC Code: stack=4, locals=2, args_size=2 0: iload_1 1: ifne 6 4: iconst_1 5: ireturn 6: iload_1 7: aload_0 8: iload_1 9: iconst_1 10: isub 11: invokevirtual #2 // Method factorial:(I)I 14: imul 15: ireturn LineNumberTable: line 4: 0 line 5: 4 line 7: 6 StackMapTable: number_of_entries = 1 frame_type = 6 /* same */
I understand that in the fifth line in the block above, stack=4 means that the stack can have at most 4 objects.
But how does the compiler compute that?
Since the initial state of the stack, as well as the effect of each instruction on it is well known, you can precisely predict, which kind of items will be on the operand stack at any time:
[ ] // initially empty
[ I ] 0: iload_1
[ ] 1: ifne 6
[ I ] 4: iconst_1
[ ] 5: ireturn
[ I ] 6: iload_1
[ I O ] 7: aload_0
[ I O I ] 8: iload_1
[ I O I I ] 9: iconst_1
[ I O I ] 10: isub
[ I I ] 11: invokevirtual #2 // Method factorial:(I)I
[ I ] 14: imul
[ ] 15: ireturn
The JVM’s verifier will do exactly that, predict the contents of the stack after each instruction, to check whether it is suitable as input of the subsequent instruction. But it helps here, to have a declared maximum size, so the verifier does not need to maintain a dynamically growing data structure or preallocate memory for the theoretically possible 64k stack entries. With the declared maximum size, it can stop when encountering an instruction that would push more than that, so it never needs more memory than declared.
As you can see, the declared maximum stack size is reached exactly once, right after the iconst_1 instruction at index 9.
This, however, does not imply that a compiler will have to perform such an instruction analysis. A compiler has a higher level model of the code derived from the source code, known as Abstract syntax tree.
This structure will be used to generate the resulting bytecode and it may also be able to predict the required stack size on that level already. But how the compiler actually does it, is implementation dependent.