Das folgende würde Stapelüberlauf für großes 'n' verursachen, und ich kann warum verstehen.Warum verursacht dieser Code einen Stack-Überlauf?
def factorial(n)
(n > 1) ? (return (n * factorial(n - 1))) : (return 1)
end
Warum verursacht der folgende Überlauf?
Ihr zweiter Algorithmus erstellt eine n -lange Kette von Lambda-Prozeduren, die jeweils einen Verweis auf die vorherige enthält. Ich weiß nicht genau, was Ruby macht, aber in einer richtig tail-rekursiven Sprache würde der Stack in deinem zweiten Algorithmus nicht überlaufen, weil k.call im Lambda auch in der Endposition ist. Wenn, wie Brians Experiment nahelegt, Ruby keine richtigen Tail Calls hat, wird die lange Kette verschachtelter Aufrufe an Lambda den Stack überschwemmen, wenn der Kopf der Kette aufgerufen wird, obwohl Ruby schlau genug ist, den Tail zu konvertieren -rekursiv factorial Aufruf in eine Schleife (= Tail-Call-Optimierung).
Die zweite Version rekursiv immer noch auf Fakultät. Ich dachte, Ruby hätte TCO nicht gemacht. Aber es bläst den Stapel nicht, bis er die Lambdas erreicht. Ich bin verwirrt. (Alle anderen sind noch verwirrter oder haben die Frage nicht gelesen. Ich stimme anderen angemessen zu.) –
"Aber es bläst den Stapel nicht, bis er die Lambdas erreicht." - Ähm? Ich verstehe nicht. –
Da das zweite Beispiel immer noch auf "faktoriell" rekursiv ist, erwartete ich, dass es den Stapel überläuft, bevor es den Basisfall von 'k.call (1)' erreicht hat. Aber im zweiten obigen Beispiel-Code überfluten die Aufrufe von "faktoriell" den Stapel nicht (selbst für sehr großes n), was ein anderes Verhalten als das erste Beispiel ist. Das zweite Beispiel erreicht diesen Basisfall und läuft nicht über, bis viele 'k.call' stattgefunden haben. Ohne TCO sehe ich nicht, wie es so weit kommt. –
Wie in der ersten Funktion können die rekursiven Aufrufe zu viele sein, damit das System sie verarbeiten kann.
In den meisten Sprachen gehen Funktionsaufrufe auf die Aufrufliste, die wirklich nur der Stapel ist. Wenn eine Funktion rekursiv aufgerufen wird, wird sie zum Aufruf-Stack hinzugefügt. Schließlich füllst du den Stapel auf und du bekommst einen Stapelüberlauf. Das ist immer eine Gefahr, wenn Sie eine rekursive Funktion ausführen, bei der Ihre Rekursionsstufe tief ist.
-1: vgl. "Das Folgende würde für große 'n' überlaufen, und ich kann verstehen, warum" –
Aus dem gleichen Grund hat der erste einen Stacküberlauf ... Der Callstack wird zu groß.
Überlauf? oder StackOverflow ?! –
-1, gehört zu uservoice. –