堆栈溢出异常

Question

我在下面编写了代码。但它会打印这个异常，我真的不知道它是什么问题，请帮助我，谢谢

代码：

    private void fillMinAverageTime() {   //T(n) = O(n^3)
    for (int i = list.size() - 2; i >= 0; i--) {
        for (int j = i + 1; j < list.size(); j++) {
            for (k = i; k <= j; k++) {
                minOne = fillMinAverageTimeArray(i, j);
                if (min == 0.0) {
                    min = minOne;
                } else if (minOne < min) {
                    min = minOne;
                }
            }
            min = 0.0;
            minOne = 0.0;
            minAverageTimeArray[i][j] = min + probability[i][j];


        }

    }
}

private double fillMinAverageTimeArray(int i, int j) {
    if (i > j) {
        return 0.0;
    }
    if (i == j) {
        return minAverageTimeArray[i][i];
    }
   System.out.println(k+","+j+","+i);//EDITED

 **return (fillMinAverageTimeArray(i, k - 1) + fillMinAverageTimeArray(k + 1, j));**//the line tat throws this exception
}

异常：

at OBST.MemoizedVersion.fillMinAverageTimeArray(MemoizedVersion.java:118)
at OBST.MemoizedVersion.fillMinAverageTimeArray(MemoizedVersion.java:118)
at OBST.MemoizedVersion.fillMinAverageTimeArray(MemoizedVersion.java:118)

编辑：它将打印：

2,3,2
3,3,2
1,2,1
2,2,1
1,3,1
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2
1,3,2

Answer 1

您已经编写了一个递归方法。您必须确保它将通过到达基本情况而终止，否则它可能会进入循环，直到发生堆栈溢出异常 - 这就是这里发生的情况。保证终止的最简单方法是始终确保每次调用都更接近基本情况。这里的基本情况是参数 i 和 j 在某个时刻必须变得相等，因此您应该尝试在每一步中使它们至少彼此更接近。

这是给出问题的行：

return (fillMinAverageTimeArray(i, k - 1) + fillMinAverageTimeArray(k + 1, j));

这只会重复使用相同的值调用您的方法。您确定您的意思不是 i + 1 和 j - 1 而不是 k + 1 和 k - 1代码>？

Answer 2

正如马克已经说过的，确保你的递归调用正确终止。

如果它仍然溢出，那么你的递归就太深了。

Hacky 解决方案，使用 JVM 的 -Xss 标志来 更改堆栈大小。

正确的解决方案是使用迭代方法并推出自己的堆栈。