Endrekursion

Definition und Grundprinzip

Eine rekursive Funktion f heißt endrekursiv, wenn ihr rekursiver Funktionsaufruf die letzte Aktion bei der Berechnung von f ist. Andere Bezeichnungen sind endständig rekursiv, iterativ rekursiv und repetitiv rekursiv; auf Englisch heißt dies tail recursive.

Entscheidend ist, dass nach dem rekursiven Aufruf keine weitere Berechnung mehr ausgeführt werden muss. Deshalb braucht das Programm die Daten des vorherigen Aufrufs nicht aufzubewahren. Der wichtigste Vorteil ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird, sofern die Endrekursion entsprechend umgesetzt oder optimiert wird.

Speicherbedarf und Optimierung

Bei einer naiv ausgeführten Rekursion wächst der Speicherverbrauch linear mit der Rekursionstiefe. Jeder Funktionsaufruf benötigt Speicher für seine Parameter und die aktuelle Continuation, also die Information darüber, wie der Programmablauf nach der Rückkehr fortgesetzt werden soll. Dazu gehören beispielsweise die Rücksprungadresse und der aktuelle stack frame auf dem Aufrufstack. Zusätzlich können funktionslokale Variablen Speicher belegen.

Bei einem endständigen Aufruf werden die gespeicherten Werte der aufrufenden Funktion nur noch dazu benötigt, die Parameter an die nächste Funktion zu übergeben. Danach kann derselbe Speicherbereich wiederverwendet werden. Ein Compiler kann deshalb endrekursive Funktionen in iterative Funktionen umformen. Dabei ersetzt er endständige Funktionsaufrufe durch Sprunganweisungen. Dieses Verfahren heißt tail call elimination. Der Speicherverbrauch der umgeformten Funktion ist unabhängig von der Rekursionstiefe.

Scheme verlangt diese automatische Umformung als Teil seiner Sprachdefinition. C, C++, C# und Java schreiben sie nicht vor, erlauben sie aber als Optimierung der jeweiligen Sprachimplementierung. Besonders häufig findet sich die Technik in Compilern für funktionale Programmiersprachen, weil dort viele Algorithmen rekursiv oder endrekursiv formuliert werden.

Die Optimierung hat einen Nachteil bei der Fehleranalyse: Werden Aufrufe durch Sprünge ersetzt und stack frames wiederverwendet, zeigt der Aufrufstack beim Anhalten an einem Haltepunkt die tatsächliche Reihenfolge der Funktionsaufrufe nicht mehr vollständig an.

Explizite Endrekursion und Verallgemeinerungen

Clojure stellt für Endrekursion den ausdrücklichen Aufruf recur bereit. Der Compiler kann dadurch erkennen, ob recur tatsächlich in der Endposition steht. Ist das nicht der Fall, weist er den Programmierer darauf hin.

Die Ersetzung endständiger Aufrufe durch Sprünge ist nicht auf den Selbstaufruf einer einzelnen Funktion beschränkt. Scheme verlangt mit der proper tail recursion auch über Funktionsgrenzen hinweg einen konstanten Speicherverbrauch. Das gilt beispielsweise für zwei Funktionen, die sich gegenseitig als jeweils letzte Aktion aufrufen.

Durch den Continuation-passing style können Programme grundsätzlich so umgeformt werden, dass alle Funktionsaufrufe endständig sind. Dazu erhält jede umgeformte Funktion eine Continuation als zusätzlichen Parameter. Diese Fortsetzung beschreibt den weiteren Programmablauf und wird von der Funktion am Ende mit dem Funktionsergebnis aktiviert. Ein solches Programm benötigt konstanten Speicherplatz für activation records, etwa auf dem Aufrufstack. Der Speicherbedarf für die ausdrücklich gespeicherten Fortsetzungen ist jedoch nicht beschränkt. Die mögliche Rekursionstiefe wird daher durch den für diese Fortsetzungen verfügbaren Speicherplatz begrenzt statt durch die Größe des Aufrufstacks.

Summenberechnung als Beispiel

Die gewöhnliche rekursive Definition der Summe der ersten n natürlichen Zahlen lautet sinngemäß:

sum(n): Falls n = 0, wird 0 zurückgegeben; sonst n + sum(n−1).

Diese Funktion ist nicht endrekursiv, weil nach dem rekursiven Aufruf noch die Addition ausgeführt werden muss. Für n = 3 entsteht die verschachtelte Rechnung 3 + (2 + (1 + 0)) = 6. Die noch ausstehenden Additionen müssen während der Rekursion gespeichert werden.

Eine endrekursive Fassung verwendet die Hilfsfunktion add_sum(m, n): Falls n = 0, gibt sie m zurück; sonst ruft sie als letzte Aktion add_sum(m+n, n−1) auf. Dabei ist m ein Akkumulator, also ein Parameter, in dem die bisherigen Zwischenergebnisse gesammelt werden. Die Funktion liefert die Summe aus m und der Summe der ersten n natürlichen Zahlen. Daher berechnet add_sum(0, n) das gewünschte Ergebnis.

Für n = 3 verläuft die Berechnung so: add_sum(0, 3) → add_sum(3, 2) → add_sum(5, 1) → add_sum(6, 0) → 6. Bei dieser Umformung wird das Assoziativgesetz der Addition natürlicher Zahlen ausgenutzt: Statt 3 + (2 + (1 + 0)) wird ((0 + 3) + 2) + 1 berechnet.

Wie jede primitiv rekursive Funktion kann diese Endrekursion auch als Iteration dargestellt werden: Man setzt m := 0 und wiederholt, solange n > 0 gilt, die Zuweisungen m := m + n und n := n − 1. Anschließend wird m zurückgegeben. Rekursive und iterative Lösungen setzen eine schrittweise Problemanalyse meist direkt um. Laut Artikel gehen Platzersparnis und Lesbarkeit dabei auf Kosten der Ausführungszeit, weshalb sich die Suche nach effizienteren Algorithmen lohnen kann. Für dieses Beispiel gibt es die direkte Formel sum(n) = (n·(n+1))/2.

Gegenseitige Endaufrufe

Endständige Aufrufe können mehrere Funktionen verbinden. Die Funktion even(n) gibt für n = 0 den Wert true zurück und ruft sonst als letzte Aktion odd(n−1) auf. Die Funktion odd(n) gibt für n = 0 den Wert false zurück und ruft sonst als letzte Aktion even(n−1) auf.

Damit lässt sich feststellen, ob eine natürliche Zahl gerade oder ungerade ist. Die beiden Funktionen rufen sich gegenseitig endständig auf. Für sich allein betrachtet ist jedoch keine von ihnen endrekursiv, weil keine Funktion sich selbst aufruft. Das Beispiel zeigt die Bedeutung der allgemeineren Optimierung endständiger Funktionsaufrufe über Funktionsgrenzen hinweg.

Allgemeine Form

Allgemein ist eine Funktion f endrekursiv, wenn sie in folgender Form definiert werden kann:

f(x) = s(x), falls R(x), f(x) = f(r(x)), sonst.

Dabei ist R die Abbruchbedingung. Die Funktionen r und s sind beliebig, dürfen aber nicht mithilfe von f definiert sein. Ist R(x) erfüllt, liefert s(x) das Ergebnis. Andernfalls verändert r(x) das Argument, und f wird mit diesem neuen Argument als letzte Berechnungsaktion erneut aufgerufen.