Why does a recursive function stop on random numbers?

Question

I wrote a small program shown below that counts how many times an infinite recursive loop will go before causing a StackOverflow error.

public class Testing {
    static void p(int i) {
        System.out.println("hello" + i);
        i++;
        p(i);
    }
    public static void main(String[] args) {
        p(1);
    }
}

The thing is, it errors on a different number each time, normally between 8000 and 9000. Can anyone explain why this happens?

EDIT: I'm using the Eclipse IDE, haven't tested it with other IDE's or the command line.

Do this number changes if setting stack size using -Xss command line parameter? — cesarse, Mar 11 '19 at 18:36

score 7 · Accepted Answer · answered Mar 11 '19 at 18:47

The JVM specs very nicely explain its behavior related to stack;

Each Java Virtual Machine thread has a private Java Virtual Machine stack, created at the same time as the thread. A Java Virtual Machine stack stores frames (§2.6). A Java Virtual Machine stack is analogous to the stack of a conventional language such as C: it holds local variables and partial results, and plays a part in method invocation and return. Because the Java Virtual Machine stack is never manipulated directly except to push and pop frames, frames may be heap allocated. The memory for a Java Virtual Machine stack does not need to be contiguous.

In the First Edition of The Java® Virtual Machine Specification, the Java Virtual Machine stack was known as the Java stack.

This specification permits Java Virtual Machine stacks either to be of a fixed size or to dynamically expand and contract as required by the computation. If the Java Virtual Machine stacks are of a fixed size, the size of each Java Virtual Machine stack may be chosen independently when that stack is created.

A Java Virtual Machine implementation may provide the programmer or the user control over the initial size of Java Virtual Machine stacks, as well as, in the case of dynamically expanding or contracting Java Virtual Machine stacks, control over the maximum and minimum sizes.

The following exceptional conditions are associated with Java Virtual Machine stacks:

If the computation in a thread requires a larger Java Virtual Machine stack than is permitted, the Java Virtual Machine throws a StackOverflowError.

If Java Virtual Machine stacks can be dynamically expanded, and expansion is attempted but insufficient memory can be made available to effect the expansion, or if insufficient memory can be made available to create the initial Java Virtual Machine stack for a new thread, the Java Virtual Machine throws an OutOfMemoryError.

An important point from this excerpt as far as your question is concerned:

This specification permits Java Virtual Machine stacks either to be of a fixed size or to dynamically expand and contract as required by the computation.

Since you are not providing a stack size, JVM tries to dynamically expand the stack size as the function gets called recursively needing more stack memory. In each run, it may find different amount of dynamic memory for its stack depending on the availability of memory on your computer at that point of run. This is the reason you see a different value for the number of iterations it takes before throwing the SO error. If you configure (using Xss<size> JVM parameter) a smaller stack size to your program, you should see mostly identical number of recursions before the SO error.

In OpenJDK (and presumably Oracle) JVM implementation the stack size is set to a default value if not provided explicitly: `java -XX:+PrintFlagsFinal | grep " ThreadStackSize"` produces `hreadStackSize = 1024 ` while running `java -Xss2m -XX:+PrintFlagsFinal | grep " ThreadStackSize"` produces `ThreadStackSize = 2048 ` — David Soroko, Mar 12 '19 at 15:28

score 1 · Answer 2 · answered Mar 11 '19 at 18:31

1

Might be related to how much real memory the computer can allocate to the program, while other programs and process are running in the computer

answered Mar 11 '19 at 18:31

riorio

6,500
7
47
100

score 1 · Answer 3 · answered Mar 11 '19 at 18:42

StackOverflowError is a error. As a error, is related to the JVM (a error is not a Exception!).

This error occurs when your stack (or method execution stack) collides with your heap size (JVM's memory).

The size of JVM's heap can be defined, but from your stack no.

score 1 · Answer 4 · answered Mar 11 '19 at 18:46

So as others have pointed out you may have to look into what jvm is beings used and from there it might also be a good exercise to know what garbage collector (how often gc is being called ) is being used as this may give you a deeper understanding not only about stack overflow error but how generally Java works. And if really keen you could implement your own small JVM and may be with a better scheme.

Andronicus · Answer 5 · 2019-03-11T21:32:26.243

0

StackOverflowError is thrown, when stack (part of memory, where method execution stack is stored) collides with heap (memory, that allocates objects, primitives etc.). You cannot predict, when the error is thrown, because the size of stack can be dynamic unless specified by -Xss flag. That's why there is no fixed method execution depth, that causes StackOverflowError.

edited Mar 11 '19 at 21:32

answered Mar 11 '19 at 18:31

Andronicus

25,419
17
47
88

1

This is quite wrong, nothing collides with anything. The OP's program runs out of stack space which which has a default value and can be explicitly set ising the `-Xss` command line option – David Soroko Mar 11 '19 at 18:53
@DavidSoroko here is a smilar explanation: https://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror. However Op didn't set stack size – Andronicus Mar 11 '19 at 19:02
1

Without referring to other answers on SO, can you explain what "stack collides with heap" actually means? After reading the documentation on `-Xss` here https://docs.oracle.com/javase/8/docs/technotes/tools/windows/java.html - please revisit your "You cannot predict..." remark. – David Soroko Mar 11 '19 at 21:23
@DavidSoroko edited – Andronicus Mar 11 '19 at 21:32

Why does a recursive function stop on random numbers?

5 Answers5