Mein Problem ist, dass ich normalerweise einen java.lang.StackOverflowError bekomme, wenn ich Rekursion verwende. Meine Frage ist - warum verursacht Rekursion Stackoverflow so viel mehr als Schleifen, und gibt es eine gute Möglichkeit, Rekursion zu verwenden, um Stacküberlauf zu vermeiden?
Dies ist ein Versuch, Problem 107 zu lösen, es funktioniert gut für ihr Beispiel, aber es fehlt der Stack-Platz für das Problem Selbst.
%Vor%Warum verursacht die Rekursion so viel mehr als loopstackoverflow
Weil jeder rekursive Aufruf etwas Speicherplatz auf dem Stapel verwendet. Wenn Ihre Rekursion zu tief ist, ergibt sich StackOverflow , abhängig von der maximal erlaubten Tiefe im Stapel.
Wenn Sie Rekursion verwenden, sollten Sie sehr vorsichtig sein und sicherstellen, dass Sie einen Basisfall bereitstellen. Ein Basisfall bei der Rekursion ist die Bedingung, auf der die Rekursion endet und der Stapel beginnt sich zu entspannen. Dies ist der Hauptgrund für die Rekursion, die StackOverflow error verursacht. Wenn es keinen Basisfall findet, wird es in eine unendliche Rekursion gehen, was sicherlich zu einem Fehler führen wird, da Stack nur endlich ist.
Jeder rekursive Aufruf verwendet etwas Speicherplatz auf dem Stapel (um irgendetwas, das für diesen einen Aufruf spezifisch ist, aufzunehmen, wie Argumente, lokale Variablen usw.). Wenn Sie also zu viele rekursive Aufrufe machen (entweder indem Sie nicht korrekt einen Basisfall angeben oder einfach zu viele rekursive Aufrufe durchführen), dann ist nicht genug Platz, um Platz für alles zu schaffen. co_de%.
Der Grund, warum Schleifen dieses Problem nicht haben, ist, dass jede Iteration einer Schleife keinen eigenen eindeutigen Raum verwendet (dh wenn ich StackOverflow mal loope, brauche ich keinen zusätzlichen Platz, um n st zu machen Schleife).
In den meisten Fällen tritt ein Stack-Überlauf auf, weil eine rekursive Methode nicht definiert wurde, mit einer nicht vorhandenen oder nicht erreichbaren Endbedingung, die dazu führt, dass der Stackspeicherplatz erschöpft ist. Eine korrekt geschriebene Rekursion sollte keinen Stapelüberlauf erzeugen.
Es gibt jedoch Situationen, in denen eine Methode einen Stack-Überlauf sogar erzeugen kann, wenn sie korrekt implementiert wurde. Zum Beispiel:
Fazit: Alles hängt von dem jeweiligen Fall ab, es ist unmöglich zu verallgemeinern, was einen Stapelüberlauf verursacht.
Bei richtiger Verwendung erzeugt die Rekursion kein StackOverflowError . Wenn dies der Fall ist, wird Ihr Basisfall nicht ausgelöst, und die Methode ruft sich ständig ad infinitum auf. Jeder Methodenaufruf, der nicht abgeschlossen wird, bleibt auf dem Stapel und überläuft ihn schließlich.
Aber Schleifen beinhalten keine Methodenaufrufe von sich selbst, so dass sich nichts auf dem Stack aufbaut und ein StackOverflowError nicht entsteht.
Rekursion verursacht einen Stapelüberlauf, weil alle vorherigen Aufrufe im Speicher sind. so ruft sich deine Methode mit neuen Parametern auf, die sich dann wieder selbst aufruft. also stapeln sich alle diese Aufrufe und normalerweise kann der Speicher ausgehen. Schleifen speichern die Ergebnisse normalerweise in einigen Variablen und rufen die Methoden auf, die wie ein neuer erneuter Aufruf von Methoden sind, nach jedem Aufruf werden die Aufrufermethoden beendet und Ergebnisse zurückgegeben.
Der Grund, warum die Rekursion Stapelüberlauf verursacht, liegt daran, dass wir nicht feststellen können, wann die Rekursion stoppen soll, und daher wird die Funktion / Methode sich selbst "für immer" nennen (bis sie den Fehler verursacht). Sie haben das gleiche Problem, selbst wenn Sie Schleifen verwenden, wenn Sie etwas wie folgt haben:
%Vor% Da flag immer wahr ist, wird die while-Schleife niemals aufhören, bis Sie den Stack-Überlauffehler erhalten.
Bei jeder Rekursionsstufe, die Sie durchlaufen, fügen Sie dem Laufzeitstapel Statusinformationen hinzu. Diese Information wird in einem Aktivierungsdatensatz gespeichert und enthält Informationen darüber, welche Variablen im Umfang sind und welche Werte sie haben. Schleifen haben bei jeder Schleife keine zusätzlichen Aktivierungsaufzeichnungen, so dass sie weniger Speicher benötigen.
In bestimmten Situationen kann die Rekursion so tief gehen, dass der Stapel überläuft, aber es gibt Möglichkeiten, dies zu verhindern. Wenn ich mit Rekursion arbeite, folge ich normalerweise diesem Format:
%Vor%Rekursion kann sehr effektiv sein und Dinge tun, die Schleifen nicht können. Manchmal kommt man einfach an einen Punkt, an dem Rekursion die offensichtliche Entscheidung ist. Was Sie zu einem guten Programmierer macht, ist, dass Sie es verwenden können, wenn es nicht völlig offensichtlich ist.
Tags und Links java recursion stack-overflow