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

Question

对于数学 class 中的作业，我得到了以下 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 class 并用作函数的输入时，将总是导致函数终止。此外，必须不可能向 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)，函数有时会returns 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 (WhosebugError 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) 的 WhosebugError，我的猜测是它非常接近您的程序可以处理的堆大小。尝试使用堆大小进行试验，我相信您遇到问题的那一点会发生变化。参见 Increasing heap space in Eclipse: (java.lang.OutOfMemoryError)

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

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

Predictability of stack overflow error in recursive function

java

stack-overflow

recursion

set