java - 递归函数中堆栈溢出错误的可预测性

Question

这个问题已经有答案了:

Why is the max recursion depth I can reach non-deterministic? (4 个回答)

已关闭 3 年前。

对于数学课的作业，我得到了以下 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(5600, 5600) 的 StackOverflowError，我的猜测是它非常接近您的程序可以使用您指定的堆大小处理的内容。尝试尝试堆大小，我确信您达到顶峰的点将会改变。参见例如Increasing heap space in Eclipse: (java.lang.OutOfMemoryError)

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