Как бороться с рекурсией Stackoverflows в Java

Question

При выполнении рекурсий для расчета перестановок или комбинаций строк требуется, чтобы на каждом уровне рекурсии создавались новые объекты, но раньше это приводит к переполнению стека, чтобы не пытаться смоделировать сценарии для массивов символов или построителя строк, но проблема возникает, когда на каждом уровне рекурсии возрастает сложность, поэтому управление массивом символов или построителем строк также становится слишком сложным.

Как разрешить такие ситуации, вот код, который я написал: -

private static int solve(int num) {

    if (num == 1) {
        return 6;
    }
    combination("", "");
    return list.size();
}

private static int combination(String ch, String prev) {

    if (!ch.isEmpty() && ch.split(" ").length == arrInput.length)
        list.add(performSum(ch));

    else {
        for (int i = 0; i < creditScore.length; i++) {
            prev = ch;
            if (ch.isEmpty())
                ch = "" + creditScore[i];
            else
                ch = ch + " " + creditScore[i];
            combination(ch, prev);
            ch = prev;
        }
    }
    return list.size();
}

Сценарий может выглядеть так: предположим, что есть общие комбинации для общего счета студентов, где: -

credits allocated ranges from 1<= N <=5
Number of subjects from  1<= N <=100
Grade points from 5<=N<=10

Therefore as an example, a combination of score could be (1*6)+(2*10)+(4*7)....N subjects

Найти общее количество различных комбинаций очков.

Answer 1

• Убедитесь, что ваша рекурсия не бесконечна. Иначе ... бессмысленно пытаться решить.

f (x) = f (x-1) будет бесконечным

• Переформулируйте проблему, постарайтесь, чтобы она вообще не взорвалась или так быстро, как это происходит. Попробуйте найти упрощения, позволяющие избежать дальнейшей обработки и т. Д.

• Заметки, сохраните результаты предыдущих запусков, чтобы вы могли иметь deeper начальную точку.

  Для f (x) = f (x-1) вы можете сохранить r [i], где i = f (i * k), другими словами, вы сохраняете результат каждые k шагов. Если x массивный, вы, вероятно, хотите хранить геометрически: k ^ i.

  Проверьте наименьшую проблему общих предков на деревьях для примера сохранения каждых k ^ i шагов.

• Рекурсию можно преобразовать в цикл, проверьте DP, Динамическое программирование. Здесь растет массив состояний, поэтому рекурсия по-прежнему невозможна.

• Если потребности рекурсии не растут геометрически и могут быть построены, например,

  а) f (x) = f (x-1), x> 0; f (0) = 1 или же б) f (x) = f (x-1) + f (x-2) + f (x-3), x> 0; f (x) = 1, x <= 0 </p>

  Вместо решения f (x) вы можете начать с f (0) и перейти к x и, после k шагов, сохранить временный прогресс в стек ожидающих работ и выйти из своей рекурсии, а затем перезапустить оценку с точки сохранения , В первом примере вам нужно только сохранить текущее значение f (x), во втором примере вам нужно знать только f (x), f (x-1) и f (x-2).

• Если потребности во временном хранилище растут с каждым вызовом, и вы не можете превратить его в проблему с фиксированными требованиями. Затем вы можете сохранить на диск. Если потребности превышают емкость вашего диска + другое хранилище, вы не можете решить эту проблему.

• Для Java используйте флаг Xmx, чтобы разрешить использовать больше оперативной памяти.

• Наконец, ваша примерная проблема выглядит как комбинаторная задача, поэтому она, скорее всего, имеет математическое решение, не требующее рекурсии, поэтому она может быть переформулирована. Если это так, проверьте combinatorics и математический обмен.