StackOverflowError in Math.Random in a randomly recursive method

Question

This is the context of my program.

A function has 50% chance to do nothing, 50% to call itself twice. What is the probability that the program will finish?

I wrote this piece of code, and it works great apparently. The answer which may not be obvious to everyone is that this program has 100% chance to finish. But there is a StackOverflowError (how convenient ;) ) when I run this program, occuring in Math.Random(). Could someone point to me where does it come from, and tell me if maybe my code is wrong?

static int bestDepth =0;
static int numberOfPrograms =0;
@Test
public void testProba(){
   for(int i = 0; i <1000; i++){
       long time = System.currentTimeMillis();
       bestDepth = 0;
       numberOfPrograms = 0;
       loop(0);
       LOGGER.info("Best depth:"+ bestDepth +" in "+(System.currentTimeMillis()-time)+"ms");
   }
}

public boolean loop(int depth){
    numberOfPrograms++;
    if(depth> bestDepth){
        bestDepth = depth;
    }
    if(proba()){
        return true;
    }
    else{
        return loop(depth + 1) && loop(depth + 1);
    }
}

public boolean proba(){
    return Math.random()>0.5;
}

.

java.lang.StackOverflowError
at java.util.Random.nextDouble(Random.java:394)
at java.lang.Math.random(Math.java:695)

. I suspect the stack and the amount of function in it is limited, but I don't really see the problem here.

Any advice or clue are obviously welcome.

Fabien

EDIT: Thanks for your answers, I ran it with java -Xss4m and it worked great.

Answer 1

Whenever a function is called or a non-static variable is created, the stack is used to place and reserve space for it.

Now, it seems that you are recursively calling the loop function. This places the arguments in the stack, along with the code segment and the return address. This means that a lot of information is being placed on the stack.

However, the stack is limited. The CPU has built-in mechanics that protect against issues where data is pushed into the stack, and eventually override the code itself (as the stack grows down). This is called a General Protection Fault. When that general protection fault happens, the OS notifies the currently running task. Thus, originating the Stackoverflow.

This seems to be happening in Math.random().

In order to handle your problem, I suggest you to increase the stack size using the -Xss option of Java.

Answer 2

As you said, the loop function recursively calls itself. Now, tail recursive calls can be rewritten to loops by the compiler, and not occupy any stack space (this is called the tail call optimization, TCO). Unfortunately, java compiler does not do that. And also your loop is not tail-recursive. Your options here are:

1. Increase the stack size, as suggested by the other answers. Note that this will just defer the problem further in time: no matter how large your stack is, its size is still finite. You just need a longer chain of recursive calls to break out of the space limit.
2. Rewrite the function in terms of loops
3. Use a language, which has a compiler that performs TCO
   1. You will still need to rewrite the function to be tail-recursive
   2. Or rewrite it with trampolines (only minor changes are needed). A good paper, explaining trampolines and generalizing them further is called "Stackless Scala with Free Monads".

To illustrate the point in 3.2, here's how the rewritten function would look like:

def loop(depth: Int): Trampoline[Boolean] = {
  numberOfPrograms = numberOfPrograms + 1
  if(depth > bestDepth) {
    bestDepth = depth
  }
  if(proba()) done(true)
  else for {
    r1 <- loop(depth + 1)
    r2 <- loop(depth + 1)
  } yield r1 && r2
}

And initial call would be loop(0).run.

Answer 3

Increasing the stack-size is a nice temporary fix. However, as proved by this post, though the loop() function is guaranteed to return eventually, the average stack-depth required by loop() is infinite. Thus, no matter how much you increase the stack by, your program will eventually run out of memory and crash.

There is nothing we can do to prevent this for certain; we always need to encode the stack in memory somehow, and we'll never have infinite memory. However, there is a way to reduce the amount of memory you're using by about 2 orders of magnitude. This should give your program a significantly higher chance of returning, rather than crashing.

We can do this by noticing that, at each layer in the stack, there's really only one piece of information we need to run your program: the piece that tells us if we need to call loop() again or not after returning. Thus, we can emulate the recursion using a stack of bits. Each emulated stack-frame will require only one bit of memory (right now it requires 64-96 times that, depending on whether you're running in 32- or 64-bit).

The code would look something like this (though I don't have a Java compiler right now so I can't test it):

static int bestDepth = 0;
static int numLoopCalls = 0;

public void emulateLoop() {
    //Our fake stack.  We'll push a 1 when this point on the stack needs a second call to loop() made yet, a 0 if it doesn't
    BitSet fakeStack = new BitSet();
    long currentDepth = 0;
    numLoopCalls = 0;

    while(currentDepth >= 0)
    {
        numLoopCalls++;

        if(proba()) {
            //"return" from the current function, going up the callstack until we hit a point that we need to "call loop()"" a second time
            fakeStack.clear(currentDepth);
            while(!fakeStack.get(currentDepth))
            {
                currentDepth--;
                if(currentDepth < 0)
                {
                    return;
                }
            }

            //At this point, we've hit a point where loop() needs to be called a second time.
            //Mark it as called, and call it
            fakeStack.clear(currentDepth);
            currentDepth++;
        }
        else {
            //Need to call loop() twice, so we push a 1 and continue the while-loop
            fakeStack.set(currentDepth);
            currentDepth++;
            if(currentDepth > bestDepth)
            {
                bestDepth = currentDepth;
            }
        }
    }
}

This will probably be slightly slower, but it will use about 1/100th the memory. Note that the BitSet is stored on the heap, so there is no longer any need to increase the stack-size to run this. If anything, you'll want to increase the heap-size.