tail-recursion
Die Tail-Rekursion ist eine rekursive Strategie, bei der eine Funktion eine gewisse Menge an Arbeit ausführt und sich dann selbst aufruft. Der "Schwanz" bezieht sich auf die Tatsache, dass die Rekursion am Ende der Funktion ist. Viele - insbesondere funktionale - Programmiersprachen-Compiler können diese Arten von Aufrufen in Iteration umwandeln, was bedeutet, dass die Tail-Rekursion in unterstützten Sprachen ohne Angst vor einem Stack-Überlauf verwendet werden kann, unabhängig von der Anzahl der Aufrufe.
3
Antworten
Wie kann ich eine tail-rekursive Liste anhängen?
Eine einfache Append-Funktion wie diese (in F #):
%Vor%
stürzt ab, wenn s groß wird, da die Funktion nicht tail rekursiv ist. Ich habe bemerkt, dass F # 's Standard Append-Funktion nicht mit großen Listen abstürzt, also muss es anders implem...
19.05.2010, 16:33
4
Antworten
Stapelüberlauf vom rekursiven Funktionsaufruf in Lisp
Ich lerne Lisp aus dem Buch "Das Land von Lisp" von Conrad Barski. Jetzt habe ich meinen ersten Stolperstein getroffen, wo der Autor sagt:
Sich so zu nennen, ist nicht nur in Lisp erlaubt, sondern oft auch
dringend empfohlen
nach dem...
07.03.2013, 10:50
1
Antwort
Ist GHC in der Lage, IO-Aktionen zu optimieren?
Führt GHC standardmäßig eine Tail-Call-Optimierung für die folgende Funktion durch? Das einzig Seltsame daran ist, dass es eine IO-Aktion rekursiv definiert, aber ich sehe nicht, warum das nicht TCO'd sein könnte.
%Vor%
27.04.2009, 03:22
1
Antwort
___ tag123recursion ___ Rekursion ist eine Art Funktionsaufruf, bei dem sich eine Funktion selbst aufruft. Solche Funktionen werden auch rekursive Funktionen genannt. Strukturelle Rekursion ist eine Methode zur Problemlösung, bei der die Lösung eines Problems von Lösungen für kleinere Instanzen des gleichen Problems abhängt.
___ tag123scheme ___ Scheme ist eine funktionale Programmiersprache in der Lisp-Familie, die dem Lambda-Kalkül sehr ähnlich ist, mit eifriger (applicative-order) -Auswertung. Bei Fragen zu URL-Schemas verwenden Sie bitte das Tag "url-scheme".
___ answer13664715 ___
Damit eine Funktion tail-rekursiv ist, muss nach der Rückgabe der Funktion nichts weiter zu tun sein, als ihren Wert zurückzugeben. Das heißt, das letzte, was im rekursiven Schritt passiert, ist der Aufruf der Funktion selbst. Dies wird im Allgemeinen durch Verwendung eines Akkumulatorparameters erreicht, um die Antwort zu verfolgen:
%Vor%
Die obige Prozedur wird zunächst mit %code% als Akkumulator wie folgt aufgerufen:
%Vor%
Beachten Sie, dass der akkumulierte Wert zurückgegeben wird, wenn der Basisfall erreicht wird, und dass der Parameter %code% an jedem Punkt des rekursiven Aufrufs aktualisiert wird. Ich musste der Prozedur einen zusätzlichen Parameter hinzufügen, aber dies kann vermieden werden, indem man eine innere Prozedur oder eine benannte %code% definiert, zum Beispiel:
%Vor%
___ tag123tailrecursion ___ Die Tail-Rekursion ist eine rekursive Strategie, bei der eine Funktion eine gewisse Menge an Arbeit ausführt und sich dann selbst aufruft. Der "Schwanz" bezieht sich auf die Tatsache, dass die Rekursion am Ende der Funktion ist. Viele - insbesondere funktionale - Programmiersprachen-Compiler können diese Arten von Aufrufen in Iteration umwandeln, was bedeutet, dass die Tail-Rekursion in unterstützten Sprachen ohne Angst vor einem Stack-Überlauf verwendet werden kann, unabhängig von der Anzahl der Aufrufe.
___ qstntxt ___
Ich lerne für einen Weihnachtstest und mache ein paar Prüfungsfragen, ich bin auf dieses Problem gestoßen, das mich ein wenig ratlos macht.
Ich kann reguläre Rekursion gut machen, aber ich kann nicht meinen Kopf darum drehen, wie ich dasselbe mit der Schwanzrekursion schreiben kann.
Reguläre Version:
%Vor%
___
Damit eine Funktion tail-rekursiv ist, muss nach der Rückgabe der Funktion nichts weiter zu tun sein, als ihren Wert zurückzugeben. Das heißt, das letzte, was im rekursiven Schritt passiert, ist der Aufruf der Funktion selbst. Dies wird im Allgemeinen durch Verwendung eines Akkumulatorparameters erreicht, um die Antwort zu verfolgen:
%Vor%Die obige Prozedur wird zunächst mit %code% als Akkumulator wie folgt aufgerufen:
%Vor%Beachten Sie, dass der akkumulierte Wert zurückgegeben wird, wenn der Basisfall erreicht wird, und dass der Parameter %code% an jedem Punkt des rekursiven Aufrufs aktualisiert wird. Ich musste der Prozedur einen zusätzlichen Parameter hinzufügen, aber dies kann vermieden werden, indem man eine innere Prozedur oder eine benannte %code% definiert, zum Beispiel:
%Vor%Ich lerne für einen Weihnachtstest und mache ein paar Prüfungsfragen, ich bin auf dieses Problem gestoßen, das mich ein wenig ratlos macht.
Ich kann reguläre Rekursion gut machen, aber ich kann nicht meinen Kopf darum drehen, wie ich dasselbe mit der Schwanzrekursion schreiben kann.
Reguläre Version:
%Vor%
Ich lerne für einen Weihnachtstest und mache ein paar Prüfungsfragen, ich bin auf dieses Problem gestoßen, das mich ein wenig ratlos macht.
Ich kann reguläre Rekursion gut machen, aber ich kann nicht meinen Kopf darum drehen, wie ich dass...
01.12.2012, 23:01
2
Antworten
Ist diese Implementierung tailrekursiv?
Ich habe in einem algorithmischen Buch gelesen, dass die Ackermann-Funktion nicht tail-rekursiv gemacht werden kann (was sie sagen ist "es kann nicht in eine Iteration umgewandelt werden"). Ich bin ziemlich verblüfft darüber, also habe ich es ve...
12.12.2010, 22:42
2
Antworten
Tail-rekursive Merge-Sortierung in OCaml
Ich versuche, eine tail-rekursive Listensortierfunktion in OCaml zu implementieren, und ich habe den folgenden Code entwickelt:
%Vor%
Aber es scheint, dass es nicht tatsächlich tail-rekursiv ist, da ich einen "Stapelüberlauf während der Ausw...
27.03.2010, 14:17
2
Antworten
Wie erstelle ich einen rekursiven Datenstrukturwert in (funktionalem) F #?
Wie kann ein Wert vom Typ:
%Vor%
Haben Sie einen Wert, der auf sich selbst verweist?
Der resultierende Wert sollte im folgenden Python-Code für eine geeignete Definition von Tree: gleich x sein
%Vor%
Bearbeiten : Offensichtlich ist m...
21.06.2010, 16:25
3
Antworten
Kann dies für den Tail Call optimiert werden? Wenn ja, aus welchem Grund geschieht dies nicht?
Ich habe die Assembly-Ausgabe in vielen Optimierungsebenen mit gcc 4.8.1 und clang 3.4.190255 überprüft, keine Optimierung für diese Art von Code.
Gibt es einen besonderen Grund, warum collatz_aux keine Tail-Call-Optimierung erhält?
%Vor...
25.09.2013, 14:28
1
Antwort
Tail Rekursion und Ausnahmen in F #
Ich habe lange gegoogelt und kann immer noch keine Antwort finden. Von dem, was ich verstehe, verwendet F # 3.0, das auf .NET 4.5 ausgeführt wird, keine Tail-Rekursion für eine rekursive Methode, wenn der Aufrufer den Aufruf in einen try / catch...
21.11.2012, 10:58
3
Antworten
Warum kann Scalac die Tail-Rekursion in bestimmten Szenarien nicht optimieren?
Warum optimiert scalac (der Scala -Compiler) die Tail-Rekursion nicht?
Code- und Compileraufrufe, die dies demonstrieren:
%Vor%
09.11.2009, 06:24