java.lang.StackOverflowError a causa della ricorsione

Question

Il mio problema è che di solito ottengo un java.lang.StackOverflowError quando uso la ricorsione. La mia domanda è: perché la ricorsione causa lo stackoverflow molto più dei loop, e c'è un buon modo di usare la ricorsione per evitare l'overflow dello stack?

Questo è un tentativo di risolvere problem 107, funziona bene per il loro esempio ma esaurisce lo spazio di stack per il problema stesso.

//-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

perché fa la ricorsione causa StackOverflow molto di più di loop fanno

Poiché ogni chiamata ricorsiva utilizza po 'di spazio sullo stack. Se la tua ricorsione è troppo profonda, il risultato sarà StackOverflow, a seconda della profondità massima consentita nello stack.

Quando si utilizza la ricorsione, è necessario fare molta attenzione e assicurarsi di fornire un base case. Un caso base in ricorsione è la condizione in base alla quale termina la ricorsione e la pila inizia a rilassarsi. Questo è il motivo principale della ricorsione che causa l'errore StackOverflow. Se non trova alcun caso base, entrerà in una ricorsione infinita, che certamente porterà a un errore, poiché Stack è solo finito.

Answer 2

Se utilizzato correttamente, la ricorsione non produce uno StackOverflowError. Se lo fa, il tuo caso base non viene attivato e il metodo continua a chiamarsi all'infinito. Ogni chiamata di metodo che non completa rimane in pila e alla fine si riversa.

Ma i loop non implicano chiamate di metodo da soli, quindi non si accumula sullo stack e non viene generato un numero StackOverflowError.

Answer 3

Ogni volta che si chiama un metodo, si consuma un "frame" dallo stack, questo frame non viene rilasciato fino a quando il metodo non ritorna, non accade lo stesso con i loop.

Answer 4

Nella maggior parte dei casi, si verifica un overflow dello stack perché un metodo ricorsivo non è definito correttamente, con una condizione di fine inesistente o irraggiungibile, che causa l'esaurimento dello spazio di memoria dello stack. Una ricorsione scritta correttamente non dovrebbe produrre un overflow dello stack.

Tuttavia, ci sono situazioni in cui un metodo può produrre uno stack overflow pari a se correttamente implementato. Ad esempio:

• Una ricorsione a crescita rapida (ad esempio, esponenziale). Ad esempio: il naive implementazione ricorsiva della funzione Fibonacci
• Un dato molto grande ingresso, che alla fine causare lo spazio dello stack da esaurire

riassumere: tutto dipende dal caso particolare, è impossibile generalizzare riguardo a cosa causa un overflow dello stack.

Answer 5

la ricorsione causa l'overflow dello stack perché tutte le chiamate precedenti sono in memoria. quindi il tuo metodo si chiama con nuovi parametri, quindi si chiama di nuovo. quindi tutte queste chiamate si accumulano e normalmente possono esaurire la memoria. I cicli memorizzano normalmente i risultati in alcune variabili e chiamano i metodi che sono come una nuova chiamata ai metodi, dopo ogni chiamata, i metodi del chiamante terminano e restituiscono i risultati.

Answer 6

Ogni chiamata ricorsiva utilizza uno spazio nello stack (per contenere qualsiasi cosa specifica per quella chiamata, come argomenti, variabili locali, ecc.). Quindi, se fai troppe chiamate ricorsive (o non fornendo correttamente un caso base o semplicemente provando a fare troppe chiamate ricorsive), allora non c'è abbastanza spazio per dare spazio a tutto questo e finisci con un StackOverflow .

Il motivo per cui i cicli non hanno questo problema è che ogni iterazione di un ciclo non usa il proprio spazio unico (vale a dire se ho ciclo n volte, non ho bisogno di spazio in più per fare il n+1 st loop).

Answer 7

Il motivo per cui la ricorsione causa l'overflow dello stack è perché non si riesce a stabilire quando la ricorsione deve interrompersi e quindi la funzione/metodo continuerà a chiamarsi "per sempre" (finché non provoca l'errore). Avrete lo stesso problema, anche se si utilizza loop, se hai qualcosa come il seguente:

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

Dal flag sarà sempre vero, il ciclo while non potrà mai fermarsi fino a quando non si dà l'errore di overflow dello stack.

Answer 8

Ogni livello di ricorsione che si scende, si aggiungono le informazioni di stato allo stack di runtime. Queste informazioni sono memorizzate in un record di attivazione e contengono informazioni come le variabili in ambito e i loro valori. I loop non hanno record di attivazione aggiuntivi ogni volta che si esegue il ciclo in modo da occupare meno memoria.

In determinate situazioni, la ricorsione può andare abbastanza in profondità da causare lo straripamento dello stack, ma esistono modi per evitare che ciò accada. Quando si lavora con la ricorsione, io di solito seguo questo formato:

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

ricorsione può essere super efficace e fare cose che loop non può. A volte arrivi ad un punto in cui la ricorsione è la decisione ovvia. Ciò che ti rende un buon programmatore è poterlo usare quando non è completamente ovvio.