Tail recursive functions are often said to "return the value of the last recursive call as the value of the function".

Tail recursion is very desirable because the amount of information which must be stored during the computation is independent of the number of recursive calls. Some modern computing systems will actually compute tail-recursive functions using an iterative process.

Das Besondere ist also: Da das Ergebnis der rekursiven Funktionsaufrufs nicht mehr modifiziert wird, kann der Stackframe der aufrufenden Funktion schon vor der Rekursion entfernt werden. Dadurch bleibt der Stackverbrauch konstant und die Funktion könnte (theoretisch) endlos rekursieren.

Voraussetzung ist natürlich ein Compiler, der solche Konstrukte erkennt und wegoptimiert.

Anmerkung: In der SpracheScheme muss garnichts erst wegoptimiert werden: Tail Recursion ist der Normalfall.

Quelle: http://www.mctr.umbc.edu/~sidhu/spring97/Lectures/Recursion/recursion/node9.html

Vorteile von TailRecursion gegenüber normaler Rekursion

• Bei normaler Rekursion wird eine der Rekursionstiefe entsprechende Anzahl von Stackframes auf dem Stack belegt. Je nach den Eigenschaften der Maschine (Prozessor oder VirtualMachine) auf der das Programm läuft, steht für den Stack nur ein relativ kleiner Teil des Hauptspeichers (Prozessor-Stack) oder der gesamte freie Speicher (Stackframes auf dem Heap) zur Verfügung. In beiden Fällen ist die Größe des Stacks und damit die Rekursionstiefe endlich. Bei richtiger Behandlung von TailRecursion ist die Anzahl der Stackframes konstant und damit eine Endlos-Rekursion möglich.
• Programme die von normaler Rekursion Gebrauch machen, ohne die maximale Rekursionstiefe zu erreichen, werden i.d.R. schneller, wenn die normale Rekursion durch TailRecursion ersetzt werden kann, weil der Overhead beim Auf-/Abbauen des Stacks eingespart wird. (Mehr hierzu in TailRecursionInCee)

• Der Hauptvorteil von TailRecursion gegenüber der Verwendung iterativer Konstrukte wie sie in den gängigen Sprachen üblich sind, ist nicht spezifisch für TailRecursion, sondern gilt für Rekursion allgemein: Es ist ein deklaratives Konzept, kein imperatives. (Siehe Rekursion und Iteration)
• Bei Software, die Unterbrechungsfrei über einen langen Zeitraum in Betrieb sein soll, ermöglicht TailRecursion den Austausch der Codebasis im Betrieb. Beispiel: In einem Server läuft eine Schleife, die eingehende Service-Anforderungen empfängt und weiterleitet. Solange diese Schleife läuft, kann die Prozedur, die in der sie implementiert ist, nicht ausgetauscht werden. Ruft aber diese Prozedur stattdessen sich selbst rekursiv auf, kann sie jederzeit gegen eine kompatible Prozedur ersetzt werden. Beim nächsten rekursiven Aufruf wird dann die neue Prozedur verwendet. Natürlich darf nicht jede eingehende Service-Anforderung zum dauerhaften Verbrauch eines Stackframes führen. Also lässt sich diese Technik nur auf einem System mit richtiger Behandlung von TailRecursion einsetzen. (So eine Update-Technologie ist z.B. in ErlangOTP implementiert.)

Diskussion

Wozu der ganze Zinnober?

Die Problematik ist, dass die akademische Wissenvermittlung versucht, das Verständnis der zugrundeliegenden Vorgänge (egal ob man sie sich jetzt in C oder Assembler vorstellt) durch abstrakte Ansprüche auf einem höheren Niveau zu ersetzen. Das an sich ist schon ein Fehler. Man möchte nicht sagen, dass zur Optimierung die Rekursion de facto außer Kraft gesetzt und durch eine Schleife bzw. ein goto ersetzt wird. Man möchte die Rekursion als etwas anderes darstellen, als was es wirklich ist: ein manchmal unvermeidliches Übel. --hl

Aber Moment!

Dass akademische Wissensvermittlung nicht immer praxisgerecht ist und dass besonders abstrakte Konzepte manchmal ungerechtfertigterweise hochgelobt werden, ist allgemein bekannt. Diese Kritik lässt sich aber im Zusammenhang mit Rekursion im Allgemeinen und TailRecursion im Speziellen nicht aufrechterhalten.

Bei der Bewertung von Programmiertechniken wie Rekursion oder der Verwendung von Sprungbefehlen dürfen wir die Betrachtung des vom Programmierer zu bearbeitenden Quelltextes und die des daraus erzeugten Maschinencodes nicht durcheinanderbringen. Selbstverständlich enthält Maschinencode für die heute üblichen Prozessoren Sprungbefehle. Kein Informatiker würde daran etwas auszusetzen haben (höchstens an den Prozessoren, aber das ist ein anderes Thema). Und selbstverständlich sollte die Formulierung des Quelltextes auf einem höheren Abstaktionsniveau erfolgen. Die Compilierung einer Rekursion im Quelltext zu einer Schleife im Maschinencode ist also nichts, dessen man sich schämen könnte -- im Gegenteil!

Rekursion kann kein "unvermeidliches Übel" sein, weil sie weder unvermeidlich, noch ein Übel ist. Jeder Algorithmus, der sich rekursiv darstellen lässt, lässt sich auch iterativ darstellen und umgekehrt. Bei der Implementation in einer bestimmten Programmiersprache hat man diese Wahl nicht immer, aber wer den Umgang mit einer Sprache gelernt hat, die eine iterative Lösung nicht erlaubt, (was sowieso für alle gängigen imperativen Sprachen nicht zutrifft,) wird Rekursion kaum als Übel bezeichnen. Wenn man die Wahl zwischen Rekursion und Iteration hat, sollte man natürlich zunächst die les-/wartbarere Lösung wählen. Welche das ist, kann von vielen Faktoren abhängen: Von der zu implementierenden Funktionalität, von der zu verwendenden Sprache, von der Qualifikation und den Gewohnheiten der Programmierer, die das Programm erstellen/lesen/bearbeiten können sollen. Wo Rekursion ein Übel wäre, verwendet man sie eben nicht. (Alles ist ein Übel, wenn es falsch eingesetzt wird.) Die Beurteilung wird oft subjektiv sein, es gibt aber Situationen, in denen eine objektive Entscheidung möglich ist, z.B. immer dann, wenn der Programmierer für die iterative Umsetzung explizit einen Stack verwenden müsste, während die rekursive Implementierung mit der impliziten Verwendung des Systemstacks auskommt (und die Systemresourcen ausreichen), ist offensichtlich die Rekursion das Gegenteil eines Übels. -- her

Ich möchte mich dem von meinem Vorredner Gesagten vollinhaltlich anschließen. (Man könnte da jetzt noch eine GANZE MENGE sagen; ja vielleicht *müsste* man das sogar, aber ich kann mich dazu gerade nicht aufraffen... ;-) // Tatsache ist, dass durch Rekursion manche Algorithmen gerade zu TRAUMHAFT einfach implementiert werden können. Und das ist ja -zumindest in meinen Augen- Sinn und Zweck von rekursiv implementierten Algorithmen. Bekanntlich beruhen ja auch einige Hochsprachen GENAU auf diesen Ansatz...: LISP, Scheme, Haskell, usw... // Da ich auch ein wenig Erfahrung mit DIESEN Sprachen habe, ist mir der Nutzen dieses Ansatzes mehr als "klar"; und ein (kritische) Diskussion darüber kommt mir beinahe lächerlich vor!

Bin wohl etwas übers Ziel hinausgeschossen. :-) Würdest du das Obige neuformieren und meine Beiträge so überarbeiten, dass sie für dich akzeptabel sind? -- hl

Habs versucht -- hoffe das Ergebnis ist ok. (-> TailRecursionInCee) -- her

Erinnert sich jemand an den deutschen Begriff für TailRecursion?

Was wäre denn mit ZyklischeRekursion? oder SchleifenRekursion?? Ich habe heute wieder mal meinen sprachschöpferischen Tag. -- hl

SchleifenRekursion? finde ich -ehrlich gesagt- genial... :-) // Ich glaube, das trifft es auch deshalb so gut, weil ja diese Form der Rekursion *direkt* durch eine äquivalente Schleife ersetzt werden kann. (Vgl. TailRecursionInCee)

• Aber Vorsicht! Eine Google-Suche ergibt folgende Bezeichnungen:
• "iterative Rekursion"
• "endständige Rekursion"
• "Endrekursion"
• wobei (keine erschöpfende Recherche) "Endrekursion" die gebräuchlichste zu sein scheint. -- hl

Ja, das scheint auch *sachlich* gerechtfertigt zu sein. Siehe Bemerkung ganz oben zum einleitenden Satz!

By relying entirely on procedure calls to express iteration, Scheme emphasized the fact that tail-recursive procedure calls are essentially goto's that pass arguments. ["Revised Report on the Algorithmic Language Scheme" - Introduction]

Frage: Bei SpracheCpp und SpracheJava kann man die Endrekursion doch nicht wegoptimieren? Man hat ja möglicherweise Referenzen in den Stackframe des Aufrufers hat (vorallem C++) oder braucht den Stack für Exceptiontracking (siehe java.lang.Throwable.printStackTrace()).