递归函数中堆栈溢出误差的可预测性

Question

对于一个数学类中的赋值，我得到了以下Java函数：

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);
    }

我们现在要展示的是，是否有可能构造一个数学集T，当它作为一个Java类实现并用作该函数的输入时，它总是会导致函数终止。此外，不能向T中添加另一个元素，这样函数仍将终止。

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

很明显，对于负参数，函数不能终止。因此，集合T必然只包含非负整数.但是对于int的大型元素，该函数也会导致堆栈溢出。这是有意义的，因为int的最大值是2,147,483,647。因此，foo(2147483647, 2147483647)将导致超过40亿个函数的递归调用。

为了了解它的发展方向，我尝试了几种不同的输入。对于x和y，我总是使用相同的输入，以使递归调用的数量最大化。这是因为如果foo(1,a)终止，但foo(a,a)没有终止，那么a不应该是集合的一部分，因为它可能导致非终止调用。

这种尝试和错误方法的奇怪之处在于，对于某些输入，例如foo(5600, 5600)，函数有时返回1，有时会导致堆栈溢出错误。

同样的电话不是每次都会导致同样的结果吗？为什么堆栈有时溢出，有时不溢出？堆栈是否与其他程序共享？有什么方法可以让这种行为更容易预测吗？是否可以按照作业中的要求指定集合T？

Answer 1

我写了一个小测试程序：

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;
    }
}

它生成这样的矩阵：

  -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

很明显，集合由{x=0，y=MININT..MAXINT}和{x=0..MAXINT，y>=0..MAXINT}组成。

关于foo的StackOverflowError (5600,5600)，我的猜测是，它非常接近您的程序所能处理的堆大小。试着用堆大小做实验，我相信你撞到屋顶的那个点会变的。见eg Increasing heap space in Eclipse: (java.lang.OutOfMemoryError)

从数学的角度来看，堆的大小应该被认为是无限的。所以我想说，以上几组的总和就是你的答案。