Tail call elimination

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.

Inhaltsverzeichnis

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

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.: Revised5 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

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Tail recursive — 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… …   Deutsch Wikipedia

  • Lisp (programming language) — Infobox programming language name = Lisp paradigm = multi paradigm: functional, procedural, reflective generation = 3GL year = 1958 designer = John McCarthy developer = Steve Russell, Timothy P. Hart, and Mike Levin latest release version =… …   Wikipedia

  • Endrekursion — 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… …   Deutsch Wikipedia

  • Endrekursiv — 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… …   Deutsch Wikipedia

  • Endrekursive Funktion — 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… …   Deutsch Wikipedia

  • UCBLogo — is a program designed by Brian Harvey and students at the University of California Berkeley (hence the name). It is one of the many programs that implement a Logo interpreter with tail call elimination …   Wikipedia

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   Wikipedia

  • Python syntax and semantics — The syntax of the Python programming language is the set of rules that defines how a Python program will be written and interpreted (by both the runtime system and by human readers). Python was designed to be a highly readable language. It aims… …   Wikipedia

  • Comparison of Prolog implementations — The following Comparison of Prolog implementations provides a reference for the relative feature sets and performance of different implementations of the Prolog computer programming language. Contents 1 Main features 2 Operating system and Web… …   Wikipedia

  • Life Sciences — ▪ 2009 Introduction Zoology       In 2008 several zoological studies provided new insights into how species life history traits (such as the timing of reproduction or the length of life of adult individuals) are derived in part as responses to… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”