StackOverflowError в Math.Random в случайном рекурсивном методе

Ответ 1

Всякий раз, когда вызывается функция или создается нестатическая переменная, стек используется для размещения и резервирования места для нее.

Теперь кажется, что вы рекурсивно вызываете функцию loop. Это помещает аргументы в стек, а также сегмент кода и обратный адрес. Это означает, что в стек помещается много информации.

Однако стек ограничен. ЦП имеет встроенную механику, которая защищает от проблем, когда данные вставляются в стек, и в конечном итоге переопределяет сам код (по мере того, как стек растет). Это называется General Protection Fault. Когда происходит эта общая ошибка защиты, ОС уведомляет текущую задачу. Таким образом, исходя из Stackoverflow.

Это похоже на Math.random().

Чтобы решить вашу проблему, я предлагаю вам увеличить размер стека с помощью опции -Xss Java.

Ответ 2

Как вы сказали, функция loop рекурсивно вызывает себя. Теперь хвостовые рекурсивные вызовы могут быть переписаны в циклы компилятором и не занимать никакого пространства стека (это называется оптимизацией хвостовых вызовов, TCO), К сожалению, компилятор java этого не делает. А также ваш loop не является хвостовым рекурсивным. Ваши варианты:

• Увеличьте размер стека, как это было предложено другими ответами. Обратите внимание, что это только отложит проблему дальше во времени: независимо от того, насколько велик ваш стек, его размер по-прежнему ограничен. Вам просто нужна более длинная цепочка рекурсивных вызовов, чтобы выйти из ограничения пространства.
• Перепишите функцию в виде циклов
• Используйте язык, в котором есть компилятор, который выполняет TCO
  • Вам все равно нужно переписать функцию, чтобы она была рекурсивной.
  • Или перепишите его с помощью батутов (требуется только незначительные изменения). Хорошая статья, объясняющая батуты и обобщающая их далее, называется " Stackless Scala с бесплатными монадами.

Чтобы проиллюстрировать точку в 3.2, вот как выглядит переписанная функция:

def loop(depth: Int): Trampoline[Boolean] = {
  numberOfPrograms = numberOfPrograms + 1
  if(depth > bestDepth) {
    bestDepth = depth
  }
  if(proba()) done(true)
  else for {
    r1 <- loop(depth + 1)
    r2 <- loop(depth + 1)
  } yield r1 && r2
}

И начальный вызов будет loop(0).run.

Ответ 3

Увеличение размера стека - прекрасное временное исправление. Однако, как доказано этим сообщением, хотя функция loop() гарантированно вернется в конце концов, средняя глубина стека, требуемая loop(), бесконечна. Таким образом, независимо от того, сколько вы увеличите количество стека, ваша программа в конечном итоге исчерпает память и сбой.

Мы ничего не можем сделать, чтобы это не допустить; нам всегда нужно каким-то образом закодировать стек в памяти, и у нас никогда не будет бесконечной памяти. Тем не менее, есть способ уменьшить объем памяти, который вы используете примерно на 2 порядка. Это должно дать вашей программе значительно более высокую вероятность возврата, а не сбой.

Мы можем сделать это, заметив, что на каждом уровне в стеке есть только одна часть информации, которую нам нужно запустить для вашей программы: фрагмент, который говорит нам, нужно ли нам снова называть loop() или нет после возвращения, Таким образом, мы можем эмулировать рекурсию, используя стек бит. Для каждого эмулируемого стекового кадра требуется только один бит памяти (сейчас требуется 64-96 раз, в зависимости от того, работаете ли вы в 32- или 64-разрядной версии).

Код будет выглядеть примерно так (хотя у меня сейчас нет компилятора Java, поэтому я не могу его протестировать):

static int bestDepth = 0;
static int numLoopCalls = 0;

public void emulateLoop() {
    //Our fake stack.  We'll push a 1 when this point on the stack needs a second call to loop() made yet, a 0 if it doesn't
    BitSet fakeStack = new BitSet();
    long currentDepth = 0;
    numLoopCalls = 0;

    while(currentDepth >= 0)
    {
        numLoopCalls++;

        if(proba()) {
            //"return" from the current function, going up the callstack until we hit a point that we need to "call loop()"" a second time
            fakeStack.clear(currentDepth);
            while(!fakeStack.get(currentDepth))
            {
                currentDepth--;
                if(currentDepth < 0)
                {
                    return;
                }
            }

            //At this point, we've hit a point where loop() needs to be called a second time.
            //Mark it as called, and call it
            fakeStack.clear(currentDepth);
            currentDepth++;
        }
        else {
            //Need to call loop() twice, so we push a 1 and continue the while-loop
            fakeStack.set(currentDepth);
            currentDepth++;
            if(currentDepth > bestDepth)
            {
                bestDepth = currentDepth;
            }
        }
    }
}

Это, вероятно, будет немного медленнее, но будет использовать около 1/100-й памяти. Обратите внимание, что BitSet хранится в куче, поэтому больше не нужно увеличивать размер стека для запуска этого. Во всяком случае, вы захотите увеличить размер кучи.

Ответ 4

Недостатком рекурсии является то, что она начинает заполнять ваш стек, что в конечном итоге приведет к переполнению стека, если ваша рекурсия слишком глубока. Если вы хотите, чтобы тест закончился, вы можете увеличить размер стека, используя ответы, приведенные в следующем потоке Stackoverflow:

Как увеличить размер стека Java?