StackOverflowException

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

Как уже сказал Марк, убедитесь, что ваш рекурсивный вызов завершается правильно.

Если он все еще переполняется, то ваша рекурсия просто слишком глубока.

Хакерское решение, используйте флаг -Xss JVM, чтобы изменить размер стека .

Правильное решение, используйте итеративный подход и катите свой собственный стек.