Why does my recursion in Java not result in a StackOverflowError?

Question

For testing StackOverflowError in Java, I wrote the following code:

package recursion_still_not_working;

public class Main {
    public static void main(String[] args) {
        // System.out.println(fibonacci(50));
        System.out.println("Result: " + factorial(3000));
    }

    public static long fibonacci(long n) {
        if (n > 1) {
            //System.out.println("calculating with " + (n - 1) + " + " + (n - 2));
            return  fibonacci(n - 1) + fibonacci(n - 2);
        } else {
            return n;
        }
    }

    public static long factorial(long n) {
        if (n > 1) {
            System.out.println("calculating with " + n);
            return n * factorial(n - 1);
        }
        System.out.println("base case reached: " + n);
        return n;
    }
}

However, only the factorial results in a StackOverflowError, while fibonacci runs through. I am thinking, that there might be some hidden optimization of my JVM going on, which picks up the case of fibonacci, but not the case of factorial.

What could explain this behavior? To be clear: I expect a stack overflow to happen, but it does not happen in one of the two cases, which confuses me. I am not surprised by the stack overflow which does happen.

My JVM is:

openjdk 11.0.3 2019-04-16
OpenJDK Runtime Environment (build 11.0.3+7-Ubuntu-1ubuntu218.04.1)
OpenJDK 64-Bit Server VM (build 11.0.3+7-Ubuntu-1ubuntu218.04.1, mixed mode, sharing)

Answer 1

The Stack Overflow Exception comes, when the Stack is full. So you have repeatedly call a functions inside the function to trigger this situation.

In fibonacci(50) call does not get such a high call depth. The call depth of fibinacci(n) is about n only. But it takes so long, because each call has to do 2 calls, so you end up with 2^n calls that must be done. But the 2 calls are done one after another so they do not add both to the stack depth.

So to get into the stack overfloe exception, you should: - choose a high enough value as parameter - set the size of the stack

So you can easily use 3000 as argument and when you call it, maybe use -Xss256k to set the stack size to 256K.