Lösung Stackoverflow in einem rekursiven Verfahren

ich eine Methode für meine Hausaufgaben geschrieben haben alle der Permutationen einer Reihe von ganzen Zahlen mit Rekursion zu berechnen. (Ich versuche, Backtracking-Algorithmus zu implementieren). aber es verursacht StackOverflowException für die Berechnung der Prämutationen von mehr als 7 Zahlen. Ich weiß nicht, wie ich dieses Problem lösen soll. implementiert es noch Backtracking, wenn ich Itration verwende?Lösung Stackoverflow in einem rekursiven Verfahren

Code:

solve(0, arr, currentS); 
//**************** 

private static void solve(int i, ArrayList<Integer> arr, int[] currentS) { 
    if (i == arr.size()) { 
     for (int j : currentS) { 
      System.out.print(j + ","); 
     } 

     System.out.println(); 

     currentS[i-1] = 0; 
     solve(i - 2, arr, currentS); 

    } else { 
     int x = nextValue(i, currentS, arr); 
     if (x != -1&&travers.isCompatible(arr, currentS.clone())) { 
      currentS[i] = x; 
      solve(i + 1, arr, currentS); 
     } 
     else if((i != 0)) 
     { 
      currentS[i] = 0; 
      solve(i - 1, arr, currentS); 
     } 
    } 
    return; 
}

nextValue() ist Methode, die nicht überprüft Duplikat zu haben, in den Kindern eines Knotens des Baumes, der nicht doppelt zu haben, von der Wurzel zu jedem verlassen

Ausnahme:

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.ArrayList.get(Unknown Source) ....

Quelle

2011-01-11 Elton.fd

Sie müssen die Rekursion für Ihre Lösung verwenden? – Bernard

Der kritische Teil der Daten befindet sich weiter unten im Stack-Trace. Bearbeiten Sie Ihre Post und fügen Sie den gesamten Stack-Trace ein –

@Bernard: Nein, es ist nicht notwendig, aber da ich Backtracking implementieren wollte, habe ich es mit der Rekursion gemacht. –

Angenommen, Ihr Algorithmus ist Sound und funktioniert ordnungsgemäß für 7 Zahlen ...

Dann brauchen Sie vielleicht mehr Stapelplatz. Dies kann in der Java-Befehlszeile durch Hinzufügen von "-Xss1024k" für eine 1-Megabyte-Stack-Größe erfolgen. Sie können das für mehr Platz erhöhen. Dies kann dir geben, was du brauchst.

Sie müssen jedoch verstehen, ist es immer eine obere Grenze für die Stapelspeicher und einen rekursiven Algorithmus trifft, dass obere Schranke riskieren. Sie können besser einen anderen Algorithmus verwenden, der den Aufruf-Stack nicht verwendet, um die Arbeit zu speichern, die Sie ausführen müssen. Manchmal ist es besser, den Heap-Space stattdessen mit einer Instanz einer Queue- oder Stack-Klasse zu verwenden, um Ihren Status zu halten.

Quelle

2011-01-11 18:24:54 rfeak

Ja, es gibt immer eine obere Grenze, aber jeder vernünftige Algorithmus für dieses Problem benötigt einen Stapelraum linear in der Länge des Arrays, aber exponentielle Ausführungszeit (da die Ausgabe eine exponentielle Größe hat). Anders ausgedrückt: Wenn Sie eine Eingabe angeben, bei der ein richtiger Algorithmus die Größenbeschränkung des Stacks erreicht, wird das Universum enden, bevor der Algorithmus beendet wird. – meriton

@meriton - ich ignoriere dieses spezielle Beispiel, ich würde lieber 10MB für eine Instanz einer Warteschlange oder Stack zuweisen, dann muss eine entsprechende Anzahl von Call-Stack-Rahmen speichern, von denen jeder größer als der entsprechende Eintrag in der Sammlung wäre. Rekursion ist elegant und oft ein interessantes Hausaufgabenproblem, aber meiner Meinung nach selten die beste Lösung. – rfeak

Offensichtlich ist Rekursion nicht für alle Probleme geeignet. Aber es ist geeignet, und sogar am besten durch irgendwelche Kriterien, die ich mir vorstellen kann, hier. – meriton

Nicht Sie zu enttäuschen, aber meine Lösung für diese Frage hat 14 Zeilen Code. Vielleicht sollten Sie Ihren Ansatz überdenken.

Hinweis: Sie nicht wirklich eine separate Liste müssen die aktuelle Permutation zu halten, können Sie permutieren (und unpermute) das Array direkt. Das bedeutet, dass Sie keinen Code benötigen, um Dubletten in der Liste zu erkennen.

Aber das Problem ist wohl eher einfach. Wikipedia writes:

Eine rekursive Funktionsdefinition hat eine oder mehr Basis Fälle bedeuten Eingang (S), für die die Funktion trivially ein Ergebnis erzeugt (ohne wiederkehrend), und einem oder mehr rekursive Fälle Bedeutung Eingabe (n), für die das Programm wiederkehrt (ruft sich selbst auf). Für Beispiel kann die faktorielle Funktion rekursiv durch die Gleichungen 0 definiert werden! = 1 und für alle n> 0, n! = n (n - 1)! Keine der Gleichungen selbst bildet eine vollständige Definition; Die erste ist der Basisfall, und die zweite ist der rekursive Fall. Die Aufgabe der rekursiven Fälle kann als komplexe Eingaben in einfachere zerlegt werden. In einer richtig gestalteten rekursive Funktion, mit jedem rekursiven Aufruf muss das Eingang Problem so vereinfacht werden, dass schließlich der Basisfall erreicht werden muss.

(Schwerpunkt meins).Ich sehe keinen Versuch zu garantieren, dass i == arr.length jemals erreicht wird. Manchmal werde ich beim Rekursieren kleiner, manchmal wird es größer, es ist durchaus möglich, dass es einfach oszilliert, ohne jemals den Basisfall zu erreichen. Mit anderen Worten, Ihr Programm würde niemals enden, aber da jeder Rekursionsschritt zusätzlichen Speicher benötigt, haben Sie keinen Speicherplatz mehr im Stack.

Quelle

2011-01-11 18:34:59 meriton

Lösung Stackoverflow in einem rekursiven Verfahren

Antwort

Verwandte Themen