решение stackoverflowException в рекурсивном методе - PullRequest
Новая
       0

решение stackoverflowException в рекурсивном методе

0 голосов
/ 11 января 2011

Я написал метод для своей домашней работы, чтобы вычислить все перестановки массива целых чисел с рекурсией.(Я пытаюсь реализовать алгоритм возврата).но это вызывает StackOverflowException для вычисления предпосылок из более чем 7 чисел.Я не знаю, как решить эту проблему.все еще реализует возврат, если я использую itration?

code: 

solve(0, arr, currentS);
//****************

private static void solve(int i, ArrayList<Integer> arr, int[] currentS) {
    if (i == arr.size()) {
        for (int j : currentS) {
            System.out.print(j + ",");
        }

        System.out.println();

        currentS[i-1] = 0;
        solve(i - 2, arr, currentS);

    } else {
        int x = nextValue(i, currentS, arr);
        if (x != -1&&travers.isCompatible(arr, currentS.clone())) {
            currentS[i] = x;
            solve(i + 1, arr, currentS);
        }
        else if((i != 0))
        {
            currentS[i] = 0;
            solve(i - 1, arr, currentS);
        }
    }
    return;
}

nextValue() - это метод, который проверяет, чтобы не иметь дубликатов в дочерних узлах дерева, илииметь дубликаты от корня до каждого отпуска

исключение: 

Exception in thread "main" java.lang.StackOverflowError
    at java.util.ArrayList.get(Unknown Source) ....

Ответы [ 2 ]

2 голосов
/ 11 января 2011

Не разочаровывать вас, но мое решение для этого вопроса имеет 14 строк кода. Возможно, вам следует пересмотреть свой подход.

Подсказка: вам не нужен отдельный список для хранения текущей перестановки, вы можете переставлять (и не переставлять) массив напрямую. Это означает, что вам не понадобится код для обнаружения дубликатов в списке.

Но ваша проблема, вероятно, более простая. Википедия пишет :

Определение рекурсивной функции имеет один или несколько базовых случаев, что означает вход (ы), для которых функция дает результат тривиально (без повторяющийся) и один или несколько рекурсивных случаи, означающие входные данные, для которых Программа повторяется (вызывает сама). За Например, факториальная функция может быть определяется рекурсивно по уравнениям 0! = 1 и для всех n> 0 n! = n (n - 1) !. Ни одно уравнение само по себе составляет полное определение; первый это базовый случай, а второй это рекурсивный случай. Работа рекурсивные случаи можно рассматривать как разбивая сложные входы в более простые. В правильно разработанном рекурсивная функция, с каждым рекурсивный вызов, проблема ввода должна быть упрощенным таким образом, чтобы в конце концов базовый случай должен быть достиг .

(выделено мое). Я не вижу никаких попыток гарантировать, что i == arr.length когда-либо будет достигнут. Иногда при повторении я становлюсь меньше, иногда он становится больше, вполне возможно, что он просто будет колебаться, даже не достигнув базового случая. Иными словами, ваша программа никогда не прекратит работу, но поскольку каждому шагу рекурсии требуется дополнительная память, вам не хватает места в стеке.

0 голосов
/ 11 января 2011

Предполагая, что ваш алгоритм корректен и работает правильно для 7 чисел ...

Тогда вам может понадобиться больше места в стеке. Это можно сделать в командной строке Java, добавив «-Xss1024k» для стека размером 1 мегабайт. Вы можете увеличить это больше для большего пространства. Это может дать вам то, что вам нужно.

Однако вы должны понимать, что ВСЕГДА существует верхняя граница для стекового пространства, и рекурсивный алгоритм рискует попасть в эту верхнюю границу. Возможно, вам лучше использовать другой алгоритм, который не использует стек вызовов для хранения работы, которую вам нужно сделать. Иногда вместо этого лучше использовать пространство кучи с чем-то вроде экземпляра класса Queue или Stack для хранения вашего состояния.

...