Predictability of stack overflow error in recursive function

Question

For an assignment in a Math class, I was given the following Java function:

public static int foo(int x, int y) {
    if (x==0) return 1;
    if (x<=y) return foo(x,y-1);
    return foo(y,x);
    }

We are now supposed to show if it is possible to construct a mathematical set T, which when implemented as a Java class and used as inputs for the function, will always lead the function to terminate. Also it must not be possible to add another element to T so that the function will still terminate.

public static T foo(T x, T y) { . . . }

It is fairly obvious that the function cannot terminate for negative parameters. Therefore set T will necessarily only include non-negative integers. But for large elements of int the function will also result in a stack overflow. That makes sense as the maximum value for int is 2,147,483,647. So foo(2147483647, 2147483647) will result in more than 4 billion recursive calls of the function.

To get a sense of where this is going, I tried out several different inputs. I always used the same inputs for x and y as that maximizes the number of recursive calls. That's because if foo(1,a) terminates but foo(a,a) doesn't, then a should not be part of the set, as it can lead to non-terminating calls.

The odd thing with this trial and error approach is, that the for some inputs, e.g. foo(5600, 5600), the function sometimes returns 1 and sometimes it leads to a stack overflow error.

Shouldn't the same call lead to the same result every time? Why does the stack sometimes overflow and sometimes not? Is the stack shared with other programs? Is there a way to make the behavior more predictable? And is it possible to specify a set T as asked in the assignment?

Since negative values will eventually overflow, they are not much different to very large values; the function would terminate on a system without stack limits. — Holger, Jan 08 '20 at 11:22

score 1 · Accepted Answer · answered Dec 23 '19 at 16:32

I wrote a little test program:

public static void main(String[] args) {
    System.out.print("    ");
    for (int x = -8; x < 8; x++) {
        System.out.printf("%2d", x);
    }
    System.out.println();

    for (int y = -8; y < 8; y++) {
        System.out.printf("%4d", y);
        for (int x = -8; x < 8; x++) {
            System.out.printf("%2d", test(x, y));
        }
        System.out.println();
    }
}

public static int test(int x, int y) {
    try {
        return foo(x, y);
    } catch (StackOverflowError e) {
        return 0;
    }
}

It generates a matrix like this:

  -8-7-6-5-4-3-2-1 0 1 2 3 4 5 6 7
-8 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
-7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
-6 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
-5 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
-4 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
-3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
-2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 5 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 6 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 7 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

It is pretty clear that the set consists of the sum of {x=0, y=MININT..MAXINT} and {x=0..MAXINT, y>=0..MAXINT}

Regarding the StackOverflowError for foo(5600, 5600) my guess is that it is very close to what your program can handle with the heap size you have given it. Try experimenting with heap size, and I'm sure the point where you hit the roof will change. See eg Increasing heap space in Eclipse: (java.lang.OutOfMemoryError)

From a mathematical point of view, your heap size should be considered infinite. So I would say the sum of the sets above is your answer.

Predictability of stack overflow error in recursive function

1 Answers1