Mit Rekursion in C#

Gibt es irgendwelche Allgemeinen Regeln, wenn Sie mit Rekursion, wie Sie zu vermeiden stackoverflows?

InformationsquelleAutor der Frage Ted Smith | 2009-03-04

  1. 32

    Wie viele Zeiten werden Sie in der Lage zu Durchlaufen, ist abhängig von:

    • Die stack-Größe (in der Regel 1 MB IIRC, aber die binary können von hand bearbeitet; ich würde nicht empfehlen, tun so)
    • Wie viel stack jeder Ebene der Rekursion verwendet (z.B. eine Methode mit 10 uncaptured Guid lokale Variablen werden nehmen mehr stack als eine Methode, die keine lokalen Variablen, zum Beispiel)
    • Der JIT, die Sie verwenden - manchmal ist die JIT - wird Verwendung tail recursion, zu anderen Zeiten wird es nicht. Die Regeln sind kompliziert, und ich kann mich nicht erinnern Sie. (Es gibt eine blog-Beitrag von David Broman zurück ab 2007und eine MSDN-Seite vom gleichen Autor/Datumaber Sie können veraltet sein.)

    Wie zu vermeiden, stack-overflows? Nicht recurse zu weit 🙂 Wenn Sie nicht ziemlich sicher sein, dass Ihr die Rekursion wird beendet, ohne dabei sehr weit (ich würde mir sorgen machen bei "mehr als 10" aber das ist sehr sicher), dann umschreiben der Rekursion zu vermeiden.

    InformationsquelleAutor der Antwort Jon Skeet

  2. 8

    Es hängt wirklich davon ab, was rekursiven Algorithmus, die Sie verwenden. Wenn es einfache Rekursion, die Sie tun können, so etwas wie dieses:

    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 ist nur wirklich nützlich, wo die Ebene der Rekursion kann definiert werden als eine logische Grenze. In dem Fall, dass dies nicht geschehen kann (wie ein Teile und herrsche-Algorithmus), müssen Sie entscheiden, wie Sie möchten, um balance, Einfachheit und Leistung und Ressourcen-Beschränkungen. In diesen Fällen kann es zu wechseln zwischen den Methoden, wenn Sie auf eine arbritrary pre-defined limit. Ein wirksames Mittel, dies zu tun, habe ich in der quicksort-Algorithmus ist, es zu tun als ein Verhältnis der Gesamt-Größe der Liste. In diesem Fall wird die logische Begrenzung ist ein Ergebnis, wenn die Bedingungen nicht mehr optimal sind.

    InformationsquelleAutor der Antwort Michael Meadows

  3. 7

    Ich bin nicht bewusst jede hart eingestellt zu vermeiden stackoverflows. Ich persönlich versuche zu gewährleisten

    1. Ich habe meine Basis Fällen Recht.

    2. Der code erreicht die base-case-irgendwann.

    InformationsquelleAutor der Antwort batbrat

  4. 4

    Wenn Sie finden, sich selbst generieren, dass viele stack-frames, möchten Sie vielleicht zu prüfen, abrollen deiner Rekursion in eine Schleife.

    Besonders wenn Sie dabei sind mehrere Ebenen der Rekursion (A->B->C->->B...) finden Sie vielleicht, dass Sie können extrahieren Sie eine dieser Ebenen in einer Schleife und Sie sparen sich einige Speicher.

    InformationsquelleAutor der Antwort DevinB

  5. 3

    Dem normalen limit, wenn nicht viel übrig ist, auf dem stack zwischen aufeinander folgenden aufrufen, um 15000-25000 Ebenen tief. 25%, wenn Sie auf IIS 6+.

    Meisten rekursiven algorhitms ausgedrückt werden kann iterativ.

    Gibt es verschiedene Wege, um zu erhöhen zugeordneten Stapelspeicher, aber ich werde es lieber lassen, finden Sie eine iterative version. 🙂

    InformationsquelleAutor der Antwort leppie

  6. 1

    Andere als einen vernünftigen stack-Größe und dafür, dass Sie sich teilen und erobern dein problem so, dass Sie ständig auf einem kleineren problem, nicht wirklich.

    InformationsquelleAutor der Antwort Jeff Moser

  7. 1

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

    http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx

    InformationsquelleAutor der Antwort tanascius

  8. 1

    Den Standard-stack-Größe für einen thread ist 1 MB, wenn Sie unter den Standard-CLR. Aber auch andere hosts ändern kann. Zum Beispiel die ASP-host ändert die Standardeinstellung von 256 KB. Dies bedeutet, dass Sie code haben, der läuft sehr gut unter VS, aber bricht, wenn Sie bereitstellen, um die real-hosting-Umgebung.

    Glücklicherweise können Sie eine stack-Größe, wenn Sie einen neuen thread erstellen mit den richtigen Konstruktor. In meiner Erfahrung ist es selten nötig, aber ich habe gesehen, ein Fall, wo dies die Lösung war.

    Können Sie den PE-header der binären selbst ändern Sie die Standard-Größe. Dies ist nützlich, wenn Sie möchten, ändern Sie die Größe für den Haupt-thread. Ansonsten würde ich empfehlen, den entsprechenden Konstruktor beim erstellen von threads.

    InformationsquelleAutor der Antwort Brian Rasmussen

  9. 1

    Schrieb ich einen kurzen Artikel über dieses hier. Im Grunde gebe ich einen optionalen parameter aufgerufen, Tiefe, hinzufügen von 1, um es jedes mal, wenn ich tiefer in Sie. In der rekursiven Methode, die ich überprüfen Sie die Tiefe für einen Wert. Wenn es größer ist als der Wert, den ich einstellen, dass ich eine exception werfen. Der Wert (Schwellenwert) wäre abhängig von Ihren Anwendungsanforderungen.

    InformationsquelleAutor der Antwort Benjamin

  10. 0

    Denken Sie daran, wenn Sie Fragen haben über system-Grenzen, dann sind Sie wahrscheinlich tun etwas schrecklich falsch.

    So, wenn Sie denken, Sie könnten eine stack-überlauf im normalen Betrieb dann müssen Sie denken, eine andere Herangehensweise an das problem.

    Es ist nicht schwer zu konvertieren, eine rekursive Funktion in eine iterative, vor allem als C# hat die Generic::Stack-collection. Durch die Stack-Typ bewegt sich der Speicher in den Programm-heap statt auf dem stack. Dies gibt Ihnen die vollständige Adresse Bereich zum speichern der rekursiven Daten. Wenn das nicht genug ist, es ist nicht allzu schwierig, die Seite die Daten auf der Festplatte. Aber ich würde ernsthaft überlegen, andere Lösungen wenn Sie auf diese Bühne.

    InformationsquelleAutor der Antwort Skizz

Schreibe einen Kommentar