Блог

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

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

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

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

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

 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
}
  

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

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

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

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

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

  1,1,2,3,5,8,13,…

  Fn = Fn-1 Fn-2

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

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

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

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

Пример:

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

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