java.lang.StackOverflowError из-за рекурсии

Question

Моя проблема в том, что я обычно получаю java.lang.StackOverflowError, когда использую рекурсию. Мой вопрос: почему рекурсия вызывает stackoverflow намного больше, чем циклы, и есть ли хороший способ использования рекурсии, чтобы избежать переполнения стека?

Это попытка решить problem 107, это хорошо работает для их примера, но заканчивается из пространства стека для проблемы.

//-1 16 12 21 -1 -1 -1 16 -1 -1 17 20 -1 -1 12 -1 -1 28 -1 31 -1 21 17 28 -1 18 19 23 -1 20 -1 18 -1 -1 11 -1 -1 31 19 -1 -1 27 -1 -1 -1 23 11 27 -1 
public class tries 
{ 
    public static int n=7,min=Integer.MAX_VALUE; 
    public static boolean[][] wasHere=new boolean[n][60000]; 
    public static void main(String[] args) 
    { 
     int[] lines=new int[n]; Arrays.fill(lines, -1000); lines[0]=0; 
     int[][] networkMatrix=new int[n][n]; 
     Scanner reader=new Scanner(System.in); 
     int sum=0; 
     for(int k=0; k<n; k++) 
     { 
      for(int r=0; r<n; r++) 
      { 
       networkMatrix[k][r]=reader.nextInt(); 
       if(networkMatrix[k][r]!=-1) sum+=networkMatrix[k][r]; 
       Arrays.fill(wasHere[k], false); 
      } 
     } 
     recursive(lines,networkMatrix,0,0); 
     System.out.println((sum/2)-min); 
    } 
    public static void recursive(int[] lines, int[][] networkMatrix, int row,int lastRow) 
    {  
     wasHere[row][value((int)use.sumArr(lines))]=true; 
     if(min<sum(lines)) return; 
     if(isAllNotMinus1000(lines)) min=sum(lines); 
     int[][] copyOfMatrix=new int[n][n]; 
     int[] copyOfLines; 
     for(int i=0; i<n; i++) 
     { 
      copyOfLines=Arrays.copyOf(lines, lines.length); 
      for(int k=0; k<n; k++) copyOfMatrix[k]=Arrays.copyOf(networkMatrix[k], networkMatrix[k].length); 
      if(i!=0&&copyOfMatrix[i][row]!=0) copyOfLines[i]=copyOfMatrix[i][row]; 
      copyOfMatrix[i][row]=0; copyOfMatrix[row][i]=0; 
      if(networkMatrix[row][i]==-1) continue; 
      if(wasHere[i][value((int)use.sumArr(copyOfLines))]) continue; 
      if(min<sum(copyOfLines)) continue; 
      recursive(copyOfLines,copyOfMatrix,i,row); 
     } 
    } 
    public static boolean isAllNotMinus1000(int[] lines) 
    { 
     for(int i=0; i<lines.length; i++) {if(lines[i]==-1000) return false;} 
     return true; 
    } 
    public static int value(int n) 
    { 
     if(n<0) return (60000+n); 
     return n; 
    } 
    public static int sum(int[] arr) 
    { 
     int sum=0; 
     for(int i=0; i<arr.length; i++) 
     { 
      if(arr[i]==-1000) continue; 
      sum+=arr[i]; 
     } 
     return sum; 
    } 
} 

Answer 1

почему рекурсии причина StackOverflow намного больше, чем петли сделать

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

При использовании рекурсии вы должны быть очень осторожны и убедиться, что вы предоставили base case. Базовый регистр в рекурсии - это условие, на основе которого заканчивается рекурсия, и стек начинает раскручиваться. Это основная причина рекурсии, вызывающая ошибку StackOverflow. Если он не найдет базовый регистр, он перейдет в бесконечную рекурсию, что, безусловно, приведет к ошибке, поскольку Stack является конечным.

Answer 2

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

Но петли не включают вызовы методов сами по себе, поэтому ничего не происходит в стеке, и StackOverflowError не приводит.

Answer 3

Каждый раз, когда вы вызываете метод, вы потребляете «фрейм» из стека, этот кадр не выводится до тех пор, пока метод не вернется, это не произойдет с петлями.

Answer 4

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

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

• Быстрорастущая (скажем, экспоненциальная) рекурсия. Например: наивная рекурсивная реализация функции Фибоначчи
• Очень большие входные данные, которые в конечном итоге привести пространство стеки быть исчерпана

Итог: все зависит от конкретного случая, это невозможно обобщите, что вызывает переполнение стека.

Answer 5

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

Answer 6

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

Причина, почему петли не имеют этой проблемы заключается в том, что каждая итерация цикла не использует свое собственное уникальное пространство (то есть, если цикл I n раз, мне не нужно дополнительное пространство, чтобы сделать n+1 й цикл).

Answer 7

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

bool flag = true; 
while (flag == true){ 
    count++; 
} 

Поскольку flag всегда будет истинным, цикл, пока не остановится, пока она не дает ошибку переполнения стека.

Answer 8

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

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

public obj MyMethod(string params) { 
    if (base-case) { 
     do something... 
    } else { 
     do something else... 
     obj result = MyMethod(parameters here); 
     do something else if needed.. 
    } 
} 

Рекурсия может быть очень эффективной и делать то, что петли не может. Иногда вы просто добираетесь до точки, где рекурсия - это очевидное решение. То, что делает вас хорошим программистом, может использовать его, когда оно не полностью obvoius.