Ошибка переполнения стека Java

Question

Я пытаюсь решить проблему, которая требует рекурсивного возврата, и мое решение вызывает ошибку переполнения стека.Я понимаю, что эта ошибка часто указывает на плохое условие завершения, но мое условие терминирования кажется правильным.Есть ли что-нибудь кроме плохого условия завершения, которое могло бы вызвать ошибку переполнения стека?Как я могу выяснить, в чем проблема?

РЕДАКТИРОВАТЬ: извините попытался опубликовать код, но это слишком некрасиво ..

Answer 1

Как говорит @irreputable, даже если ваш код имеет правильное условие завершения, может оказаться, что проблема просто слишком велика для стека (так что стек исчерпан до того, как условие будет достигнуто). Существует также третья возможность: ваша рекурсия вступила в цикл. Например, при поиске в глубине в графе, если вы забудете пометить узлы как посещенные, вы в конечном итоге будете идти по кругу, возвращаясь к узлам, которые вы уже видели.

Как вы можете определить, в какой из этих трех ситуаций вы находитесь? Попытайтесь описать «местоположение» каждого рекурсивного вызова (обычно это включает параметры функции). Например, если вы пишете алгоритм графа, где функция вызывает себя на соседних узлах, то имя узла или индекс узла является хорошим описанием того, где находится рекурсивная функция. В верхней части рекурсивной функции вы можете напечатать описание, а затем вы увидите, что делает функция, и, возможно, вы сможете определить, правильно ли она работает или нет, или она идет по кругу. Вы также можете сохранить описания в HashMap, чтобы определить, вошли ли вы в круг.

Answer 2

Вместо использования рекурсии у вас всегда может быть цикл, использующий стек. Например. вместо (псевдокод):

function sum(n){
  if n == 0, return 0
  return n + sum(n-1)
}

Использование:

function sum(n){
  Stack stack
  while(n > 0){
    stack.push(n)
    n--
  }
  localSum = 0
  while(stack not empty){
    localSum += stack.pop()
  }
  return localSum
}

В двух словах, имитируйте рекурсию, сохраняя состояние в локальном стеке.

Answer 3

Как уже упоминались другие парни, для этого может быть несколько причин:

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

• Ваша память слишком мала, чтобы хранить количество рекурсивных вызовов в стеке. Большие числа Фибоначчи могут быть хорошим примером здесь. Просто к вашему сведению Фибоначчи выглядит следующим образом (иногда начинается с нуля):

  1,1,2,3,5,8,13, ...

  Fn = Fn-1 + Fn-2

  F0 = 1, F1 = 1, n> = 2

Answer 4

Вы можете использовать опцию -Xss, чтобы дать вашему стеку больше памяти, если ваша проблема слишком велика, чтобы ее можно было исправить в предельном размере стека по умолчанию.

Answer 5

Существует две распространенных ошибки кодирования, которые могут привести к тому, что ваша программа попадет в бесконечный цикл (и, следовательно, вызвать переполнение стека):

• Плохое условие завершения
• Неверный рекурсивный вызов

Пример:

public static int factorial( int n ){
    if( n < n ) // Bad termination condition
        return 1;
    else
        return n*factorial(n+1); // Bad recursion call
}

В противном случае ваша программа могла бы просто функционировать нормально, а стек слишком мал.

Answer 6

Если ваш код правильный, то стек просто слишком мал для вашей проблемы.У нас нет настоящих машин Тьюринга.