Tail recursive

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 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 — 1. noun A style of programming in which all functions are written so that recursive calls are made nowhere but immediately before function return. 2. adjective A program or function that is written or can be rewritten in a tail recursive style …   Wiktionary

  • Tail recursive parser — Tail recursive parsers are derived from the more common Recursive descent parsers. Tail recursive parsers are commonly used to parse left recursive grammars. They use a smaller amount of stack space than regular recursive descent parsers. They… …   Wikipedia

  • Tail recursion — In computer science, tail recursion (or tail end recursion) is a special case of recursion in which the last operation of the function is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with… …   Wikipedia

  • Recursive descent parser — A recursive descent parser is a top down parser built from a set of mutually recursive procedures (or a non recursive equivalent) where each such procedure usually implements one of the production rules of the grammar. Thus the structure of the… …   Wikipedia

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

  • Recursive type — In computer programming languages, a recursive type is a data type for values that may contain other values of the same type.An example is the list type, in Haskell: data List a = Nil | Cons a (List a) This indicates that a list of a s is either… …   Wikipedia

  • tail recursion — noun The technique of writing a function so that recursive calls are only done immediately before function return, particularly when recursive control structures are used in place of iterative ones …   Wiktionary

  • Recursion (computer science) — Recursion in computer science is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. [cite book last = Epp first = Susanna title = Discrete Mathematics with Applications year=1995… …   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

  • Quicksort — Infobox Algorithm class=Sorting algorithm Quicksort in action on a list of numbers. The horizontal lines are pivot values. data=Varies time=O(nlog n) on average space=Varies by implementation optimal=Sometimes Stability= [Sorting… …   Wikipedia

Share the article and excerpts

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