•  03-07-2019
  •  | 
  •  

Frage

Gibt es allgemeine Regeln, wenn Rekursion, wie Stack-Überlauf zu vermeiden?

War es hilfreich?

Lösung

Wie oft sind Sie in der Lage sein wird rekursiv abhängig von:

  • Die Stack-Größe (die in der Regel 1MB IIRC ist, aber die binäre kann von Hand bearbeitet werden, würde ich nicht tun, so empfehlen)
  • Wie viel Stack jede Ebene der Rekursion verwendet (ein Verfahren, das mit 10 nicht erfaßten Guid lokalen Variablen wird mehr Stapel eingenommen hat, als ein Verfahren, das keine lokalen Variablen hat, zum Beispiel)
  • Die JIT Sie verwenden - manchmal die JIT wird Verwendung Endrekursion, ein anderes Mal wird es nicht. Die Regeln sind kompliziert und ich kann sie nicht mehr erinnern. (Es gibt ein Blog-Post von David Broman zurück von 2007 und eine MSDN-Seite vom selben Autor / Datum , sie können aber mittlerweile veraltet sein.)

Wie Stapelüberlauf zu vermeiden? Rekursion nicht zu weit :) Wenn Sie nicht einigermaßen sicher sein können, dass Ihre Rekursion ohne ging sehr weit beenden wird (I bei „mehr als 10“ besorgt sein würde, obwohl das sehr sicher ist), dann es neu schreiben Rekursion zu vermeiden.

Andere Tipps

Es hängt wirklich davon ab, welche rekursiven Algorithmus Sie verwenden. Wenn es einfach Rekursion ist, können Sie etwas tun: 

public int CalculateSomethingRecursively(int someNumber)
{
    return doSomethingRecursively(someNumber, 0);
}

private int doSomethingRecursively(int someNumber, int level)
{
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber))
        return someNumber;
    return doSomethingRecursively(someNumber, level + 1);
}

Es ist erwähnenswert, dass dieser Ansatz wirklich ist nur sinnvoll, wenn die Höhe der Rekursion als logische Grenze definiert werden kann. Im Fall, dass dies nicht (wie ein Teil und Herrsche-Algorithmus) auftreten kann, müssen Sie entscheiden, wie Sie Einfachheit im Vergleich Leistung im Vergleich zu Ressourcenbeschränkungen ausgleichen wollen. In diesen Fällen können Sie zwischen Methoden wechseln, sobald Sie eine arbiträre vordefinierte Grenze erreicht. Ein wirksames Mittel, dies zu tun, die ich im quicksort Algorithmus verwendet habe, ist es als ein Verhältnis der Gesamtgröße der Liste zu tun. In diesem Fall ist die logische Grenze ergibt sich aus, wenn die Bedingungen nicht mehr optimal sind.

Ich bin keine Kenntnis von hart eingestellt stackoverflows zu vermeiden. Ich persönlich versuche, um sicherzustellen, -
1. Ich habe meinen Grund Fälle richtig.
2. Der Code erreicht den Basisfall an einem gewissen Punkt.

Wenn Sie finden selbst zu erzeugen, dass viele Stack-Frames, könnten Sie Ihre Rekursion in einer Schleife betrachten wollen Abrollen.

Vor allem, wenn Sie mehrere Ebenen der Rekursion (A-> B-> C-> A-> B ...) tun, könnten Sie feststellen, dass Sie eine dieser Ebenen in eine Schleife extrahieren und sich etwas Speicher sparen.

Die normale Grenze, wenn nicht viel auf dem Stapel zwischen aufeinanderfolgenden Aufrufen gelassen wird, ist um 15.000 bis 25.000 Ebene tief. 25%, wenn Sie sind auf IIS 6 +.

Die meisten rekursiven algorhitms kann iterativ ausgedrückt werden.

Es gibt verschiedene Art und Weise zugeordnet Stapelspeicherplatz zu erhöhen, aber ich werde nicht lassen Sie zunächst eine iterative Version. :)

Anders als eine angemessene Stapelgröße und dafür, dass Sie Teile und herrsche Ihr Problem, so dass Sie auf einem kleineren Problem ständig arbeiten, nicht wirklich.

Ich dachte nur, der Schwanz-Rekursion, aber es stellte sich heraus, dass C # nicht unterstützt. Doch die .Net-Framework-scheint es zu unterstützen:

http: // blogs .msdn.com / abhinaba / Archiv / 2007/07/27 / Schwanz-Rekursion-on-net.aspx

Die Standard-Stackgröße für einen Thread ist 1 MB, wenn Sie unter dem Standard CLR laufen. Jedoch kann, dass andere Hosts ändern. Zum Beispiel ändert sich die ASP-Host die Standard zu 256 KB. Dies bedeutet, dass Sie Code haben können, die sehr gut unter VS läuft, aber bricht, wenn man es auf die reale Hosting-Umgebung bereitstellen.

Zum Glück können Sie eine Stack-Größe angeben, wenn Sie einen neuen Thread erstellen, indem Sie den richtigen Konstruktor. Nach meiner Erfahrung ist es selten nötig, aber ich habe einen Fall gesehen, wo dies die Lösung war.

Sie können die PE-Header des binären bearbeiten selbst die Standardgröße zu ändern. Dies ist nützlich, wenn Sie die Größe des Haupt-Thread geändert werden sollen. Sonst würde ich mit dem entsprechenden Konstruktor empfehlen, wenn Threads zu erstellen.

ich einen kurzen Artikel über das geschrieben hat? hier . Grundsätzlich gebe ich einen optionalen Parameter aufgerufen, die Tiefe, die Zugabe von 1 bis es jedes Mal, wenn ich tiefer hinein gehen. Innerhalb der rekursiven Methode prüfe ich die Tiefe für einen Wert. Wenn er größer ist als der Wert I gesetzt ist, werfe ich eine Ausnahme. Der Wert (Schwellenwert) würde auf Ihre Anwendungen Bedürfnisse abhängig sein.

Denken Sie daran, wenn Sie über Systemgrenzen fragen haben, dann sind Sie wahrscheinlich etwas schrecklich falsch zu machen.

Also, wenn Sie denken, Sie könnten einen Stapelüberlauf im Normalbetrieb erhalten, dann müssen Sie eine andere Herangehensweise an das Problem denken.

Es ist nicht schwierig, eine rekursive Funktion in einem iterativen umzuwandeln, insbesondere als C # Generic :: Stapel Sammlung. den Stapeltypen unter Verwendung bewegt den Speicher in das Heap-Programm verwendet anstelle des Stapels. Dies gibt Ihnen den vollständigen Adressbereich die rekursiven Daten zu speichern. Wenn das nicht genug ist, dann ist es nicht allzu schwer zu Seite der Daten auf der Festplatte. Aber ich würde ernsthaft andere Lösungen in Betracht ziehen, wenn Sie zu diesem Zeitpunkt erhalten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top