Tail call elimination

Eine rekursive Funktion f ist endrekursiv (englisch: tail recursive) (auch endständig rekursiv, iterativ rekursiv, repetitiv rekursiv), wenn der rekursive Funktionsaufruf die letzte Aktion zur Berechnung von f ist.^[1] Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Platz zur Verwaltung der Rekursion benötigt wird.

Entfernen von endständigen Funktionsaufrufen

Bei der naiven Abarbeitung einer rekursiven Funktion steigt der Speicherplatzverbrauch linear mit der Rekursionstiefe, da bei jedem Funktionsaufruf Speicherplatz für das Aufzeichnen der aktuellen Continuation des Programmflusses und der Funktionsparameter belegt wird (etwa zum Sichern der Rücksprungadresse und des aktuellen stack frame auf dem Aufrufstack). Außerdem kann während der Abarbeitung der aufgerufenen Funktion weiterer Speicherplatz für das Ablegen von funktionslokalen Variablen belegt werden. Bei einem endständigen Funktionsaufruf werden die im für die aufrufende Funktion belegten Speicherbereich abgelegten Werte aber nur noch für die Parameterübergabe an die endständig aufgerufene Funktion benötigt, so dass dieser Speicherbereich wiederverwendet werden kann. Somit können endrekursive Funktionen automatisch (etwa im Rahmen eines Optimierungsschrittes des Compilers) in iterative Funktionen umgeformt werden, deren Speicherplatzverbrauch bei der Abarbeitung unabhängig von der Rekursionstiefe ist. Bei der Umformung werden die Aufrufe der endständigen Funktion durch entsprechende Sprunganweisungen ersetzt (tail call elimination).

Einige Programmiersprachen wie etwa Scheme verlangen die automatische Umformung von endrekursiven Funktionen in iterative Funktionen als Teil ihrer Sprachdefinition. Andere Programmiersprachen wie etwa C, C++ und C# sowie Java verlangen diese Umformung nicht, lassen sie aber für die jeweilige Sprachimplementierung als Optimierung zu. Als Optimierung ist diese Technik häufig in Compilern für funktionale Programmiersprachen zu finden, da bei Verwendung eines funktionalen Programmierstils die rekursive/endrekursive Formulierung für viele Algorithmen besonders häufig ist und darum solchen Formulierungen im Rahmen der Programmoptimierung beim Übersetzen durch einen Compiler besondere Beachtung zukommt.

Das automatische Ersetzen von Funktionsaufrufen durch Sprunganweisungen mit Wiederverwendung des aktuellen stack frame erschwert die Ablaufverfolgung eines Programms bei der Fehleranalyse, da der Aufrufstack beim Unterbrechen eines laufenden Programms an einem Haltepunkt die Aufrufreihenfolge der Funktionen nicht vollständig wiedergibt.

Anwendbarkeit und Verallgemeinerung

Die Anwendbarkeit der Technik zur Ersetzung von endständigen Funktionsaufrufen durch Sprünge ist nicht auf endrekursive Funktionen beschränkt. Scheme verlangt beispielsweise auch über Funktionsgrenzen hinweg die Ausführung von endständigen Funktionen mit konstantem Speicherplatzverbrauch (proper tail recursion), beispielsweise für zwei Funktionen, die sich gegenseitig endständig aufrufen.^[2][3]

Durch den Übergang zu Continuation-passing style lassen sich prinzipiell Programme so umformen, dass alle Funktionsaufrufe durch endständige Aufrufe ersetzt werden. Dazu müssen jedoch alle aufgerufenen Funktionen so umgeformt werden, dass sie eine Continuation als Parameter übernehmen, die sie dann explizit mit Übergabe des Funktionsergebnisses zur Ausführung des weiteren Programmlaufs endständig aktivieren. Bei der Ausführung eines solchermaßen umgeformten Programms wird dann konstanter Speicherplatz für die Ablage der activation records (etwa auf dem Aufrufstack) benötigt, aber der für die Ablage der Fortsetzungen benötigte Speicherplatz ist nicht beschränkt. Als Folge dieser Umformung ist dann die mögliche Rekursionstiefe einer Routine durch den zur Ablage der Fortsetzungen verfügbaren Speicherplatz beschränkt statt durch die Größe des Aufrufstacks.^[4]

Beispiele

Gegeben sei die rekursive Funktion sum, die die Summe der ersten n natürlichen Zahlen berechnet:

 sum(n)
   if n=0
     return 0
   else
     return n + sum(n-1)

Da nicht der rekursive Funktionsaufruf sondern die Addition die letzte Aktion bildet, handelt es sich nicht um eine endrekursive Funktion. Die Berechnung von sum(3) würde damit folgende Schritte beinhalten:

sum(3) = 3 + sum(2)
 sum(2) = 2 + sum(1)
  sum(1) = 1 + sum(0)
   sum(0) = 0
  sum(1) = 1 + 0 = 1
 sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6

In diesem Fall ist jedoch eine Umformung in eine endrekursive Darstellung möglich.

 sum(n)
   return add_sum (0, n)
 
 add_sum(m, n)
   if n=0 
     return m
   else
     return add_sum (m+n, n-1)

Die endrekursive Hilfsfunktion add_sum empfängt zwei Parameter m und n und liefert als Ergebnis die Summe aus m und der Summe der ersten n natürlichen Zahlen. Der Aufruf add_sum (0, n) liefert somit das gewünschte Ergebnis, die Summe der ersten n natürlichen Zahlen. Während des Ablaufs der Endrekursion in add_sum werden die Zwischenergebnisse im m-Parameter akkumuliert. In dieser endrekursiven Formulierung würde die Berechnung von sum(3) etwa folgende Schritte beinhalten:

sum(3) = add_sum(0, 3)
       = add_sum(3, 2)
       = add_sum(5, 1)
       = add_sum(6, 0)
       = 6

Bei der Umformung wurde implizit das Assoziativgesetz für die Addition natürlicher Zahlen ausgenutzt. Die ursprüngliche Definition von sum(n) berechnete sum(3) als

3 + (2 + (1 + 0))

Die umgeformte Formulierung berechnet denselben Wert als

((3 + 2) + 1) + 0

Wie jede rekursive Funktion lässt sich die Endrekursion mittels Iteration darstellen.

 sum(n)
    m := 0
    
    while (n > 0) do
      m   := m + n
      n   := n - 1
    end-while
    return m

Rekursive wie iterative Lösungen stellen meist eine direkte Umsetzungen eines Problems dar, welches schrittweise analysiert wurde. Platzersparnis und Lesbarkeit gehen dabei auf Kosten der Ausführungszeit. Vielfach lohnt daher die Suche nach effizienteren Algorithmen. So ist der beste Algorithmus zur Berechnung des Beispielfalles vor allem durch die „Gaußsche Schulgeschichte“ bekannt geworden:

 sum(n) = (n*(n+1)) / 2

Als Beispiel für Endrekursion mit mehreren beteiligten Funktionen hier zwei Funktionen even und odd zur Feststellung ob eine gegebene natürliche Zahl gerade oder ungerade ist.

 even(n)
   if n=0
     return true
   else
     return odd(n-1)

 odd(n)
   if n=0
     return false
   else
     return even(n-1)

Die beiden Funktionen rufen sich gegenseitig endständig auf. Für sich genommen ist keine der beiden Funktionen endrekursiv.

Verallgemeinerung

Allgemein ist eine Funktion f endrekursiv, wenn sie sich auf folgende Weise definieren lässt:

$f(x) = \begin{cases} f(r(x)), & \mbox{falls }R(x) \\ s(x), & \mbox{sonst } \end{cases}$

Dabei sind r und s beliebige nicht mittels f definierte Funktionen und R die negierte Abbruchbedingung.

Siehe auch

• Platzkomplexität

Referenzen

1. ↑ Harold Abelson, Gerald Jay Sussman, sowie Julie Sussman: Linear Recursion and Iteration. In: Structure and Interpretation of Computer Programs. Second edition, The MIT Press 1996, ISBN 0-262-51087-1
2. ↑ Richard Kelsey, William Clinger, Jonathan Rees et al.: Revised⁵ Report on the Algorithmic Language Scheme. In: Higher-Order and Symbolic Computation. 11, Nr. 1, August 1998, S. 7-105. doi:10.1023/A:1010051815785
3. ↑ William Clinger: Proper tail recursion and space efficiency, Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, Juni 1998, S. 174-185
4. ↑ Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes: Essentials of Programming Languages. Second edition, MIT Press 2001, ISBN 0262062178