Ich habe den Pseudocode hier in C #, und rekursiv 10.000 mal wiederholen. Aber ich bekomme einen C # Laufzeitfehler, StackOverflow Exception nach 9217 mal. Wie kann ich das verhindern?
BEARBEITEN Wenn es jemandem hilft, hier ist der Code:
%Vor%EDIT2 Also scheint jeder zuzustimmen, dass ich das in iterative konvertieren muss ... kann irgendjemand etwas Code geben? Ich kann anscheinend keinen iterativen Code schreiben, der funktioniert ...
BEARBEITEN Danke an Paul Rieck für diese Antwort, die ich getestet habe, und es funktioniert:
%Vor%Der "c # -Compiler" kompiliert das gut. Zur Laufzeit kann jedoch eine StackOverflow-Ausnahme auftreten (auf meinem Computer funktionieren 10.000, aber später).
Dies ist keine "unendliche Rekursionsausnahme" - der Stapelüberlauf ist genau das, was er sagt; Das Aufrufen einer Methode bedeutet, Informationen auf den Stapel zu stellen und sie zu entfernen, wenn der Anruf zurückkehrt. Sie haben 10.000 Aufrufe und keiner ist zurückgekehrt, daher ist der Stapel voll und die Ausnahme wird ausgelöst.
Sie können dies in diesem speziellen Fall relativ einfach beheben, indem Sie die Rekursion entfernen und iterativ ausführen. Im allgemeinen Fall gibt es Möglichkeiten, die Rekursion über Iteration, Tail-Recursion-Optimierung und Continuation Passing zu entfernen.
Hier ist eine schnelle direkte Übersetzung in einen iterativen Stil:
%Vor%So scheint jeder zustimmen, dass ich dies in iterative konvertieren muss ... kann jemand etwas Code geben? Ich kann anscheinend keinen iterativen Code schreiben, der funktioniert ...
Fragen Sie nach einem Fisch oder fragen Sie, wie man Fische fängt? Wenn der Zweck dieser Übung darin besteht, zu lernen, wie man rekursiven Code in iterativen Code umwandelt, ist es nicht gut, wenn man nur die Antwort erhält.
Um rekursiven Code in iterativen Code zu konvertieren, gibt es viele Möglichkeiten, dies zu tun. Der einfachste Weg ist in diesem Fall, das Muster einfach auszuarbeiten. Was macht der Code? Es berechnet:
%Vor%Jetzt können Sie eine Schleife schreiben, die das berechnet? Sicher.
%Vor%Das ist der einfachste Weg, es zu tun. Aber es gibt viele Möglichkeiten, dieses Problem zu lösen.
Sie könnten einen Aggregator verwenden. Betrachten Sie die Operation "total"; Das ist ein Beispiel für einen Aggregator. Sie haben eine Abfolge von Dingen und Sie behalten eine laufende Summe von ihnen bei und akkumulieren das Ergebnis in einem Akkumulator. Die Standardabfrageoperatoren haben eine Aggregationsoperation für Sie bereitgestellt:
%Vor%Oder Sie könnten Ihren Algorithmus rekursiv halten, aber den Stack-Überlauf beseitigen durch:
Die Erklärung dieser Techniken dauert zu lange für eine Antwort. Ich habe eine sechsteilige Blogserie darüber, wie man diese Techniken benutzt, um rekursive Programme in Programme zu verwandeln, die nicht viel Stack verbrauchen; Fange an, es hier zu lesen:
Verwenden Sie keine Rekursion. Dies ist ein guter Beispielfall, in dem Sie nicht rekursiv sein sollten, da Sie einen Call-Stack-Überlauf verursachen.
Sie können das leicht in nicht-rekursiv konvertieren.
Um auf das zu kommen, was alle anderen hier sagen - das ist ein Stack Overflow (Frage! Eine Stack Overflow Frage auf StackOverflow. Dies könnte einen Stack verursachen...)
Jedenfalls schiebt es bei jedem Aufruf der rekursiven Methode den Stack, was bedeutet, dass es sich selbst auf den Stack verweist, so dass beim Aufruf des letzten Aufrufs von CalculatePi alle abgerufen werden können Rest der Anrufe.
Der Stapel ist keine unendliche Ressource. Jedes Drücken auf den Stapel verbraucht etwas Speicher, und wenn Sie alles verwenden, erhalten Sie einen Stapelüberlauf.
Der rekursive Aufruf ist nicht tail-rekursiv, und selbst wenn dies der Fall wäre, würde dies nicht helfen, da der C # -Compiler derzeit tail-rekursive Aufrufe nicht optimiert. EDIT: Wie von Eric Lippert und Gabe hingewiesen, könnte die CLR wählen Heck-Anrufe zu generieren, auch wenn explizite Tail-Call-Anweisungen nicht in der emittierten IL sind.
Bitte tu das nicht. Nur zum Spaß:
%Vor%