Wie funktioniert diese naive rekursive Fibonacci-Implementierung nicht im Stack-Overflow?

Question

Wie funktioniert diese naive rekursive Fibonacci-Implementierung nicht im Stack-Overflow?

7

Als Witz vor ein paar Monaten, suchte ein Mitarbeiter von mir, "den Hitzetod des Universums zu beschleunigen", indem er die Fibonacci-Zahlen unter Verwendung dieses Exponentialalgorithmus berechnete:

%Vor%

Wie bewirkt das nicht einen Stackoverflow in C #? Wir schafften es, zu Fib (52) zu kommen, bevor wir aufgaben (und Fib (51) brauchte viele Stunden). Ich würde denken, dass dies den Stapel hart genug schlagen würde, um einen Stapelüberlauf zu verursachen, da die CLR standardmäßig nur 1M dem Stapel zuordnet. Ich bin mir auch ziemlich sicher, dass dies nicht für Tail-Rekursion geeignet ist.

algorithm .net c# stack-overflow fibonacci

Earlz 07.03.2013, 20:03

quelle

2 Antworten

2

Die naive Fibonacci-Implementierung erzeugt in der Tat eine große Anzahl von Funktionsaufrufen (tatsächlich dem Ergebnis gleich), aber sie rekurriert nicht sehr tief. Die maximale Rekursionstiefe ist n .

Ben Voigt 07.03.2013 20:09

quelle

Tags und Links algorithm .net c# stack-overflow fibonacci

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Formulareingabe Validierung mit Meteor [geschlossen]

score 20 · Accepted Answer

Die rekursiven Aufrufe werden nicht gleichzeitig, sondern sequentiell berechnet, was bedeutet, dass Fib(n - 2) erst nach Fib(n - 1) berechnet wird (oder umgekehrt). Dies bedeutet, dass, obwohl Sie 2^n rekursive Aufrufe erstellen, nur n gleichzeitig aktiv ist. Daher benötigt Fib(52) nur Platz für 52 stackframes von Fib , was keinen merklichen Stack-Platz benötigt.