imported>KlartextJan: /* Einzelnachweise Links*/

2024-03-07T14:56:29Z

Einzelnachweise Links

Neue Seite

Eine [[Rekursion|rekursive]] [[Funktion (Programmierung)|Funktion]] ''f'' ist '''endrekursiv''' ({{enS|''tail recursive''}}; auch '''endständig rekursiv''', '''iterativ rekursiv''', '''repetitiv rekursiv'''), wenn der rekursive Funktionsaufruf die letzte Aktion zur Berechnung von ''f'' ist.<ref name="sicp">Harold Abelson, Gerald Jay Sussman, sowie Julie Sussman: {{Webarchiv |url=http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 |text=''Linear Recursion and Iteration'' |wayback=20060903155101 |archiv-bot=}}. In: ''[[Structure and Interpretation of Computer Programs]]''. Second edition, The MIT Press 1996, ISBN 0-262-51087-1</ref> Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird.

== Automatisches Entfernen von endständigen Funktionsaufrufen ==
Bei der naiven Abarbeitung einer rekursiven Funktion steigt der [[Arbeitsspeicher|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 [[Compiler]]s) in [[iterative Funktion]]en 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 [[Sprunganweisung]]en 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 (Programmiersprache)|C]], [[C++]] und [[C-Sharp|C#]] oder [[Java (Programmiersprache)|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 Programmiersprache]]n 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 [[Debugging|Fehleranalyse]], da der Aufrufstack beim Unterbrechen eines laufenden Programms an einem [[Haltepunkt (Programmierung)|Haltepunkt]] die Aufrufreihenfolge der Funktionen nicht vollständig wiedergibt.

== Explizite Endrekursion ==
Die Programmiersprache [[Clojure]] bietet den expliziten Aufruf <code>recur</code> für Endrekursion. Dies hat den Vorteil, dass der Compiler es erkennt, wenn der Aufruf nicht aus der Endposition erfolgt, und den Programmierer darauf hinweist.<ref>{{Internetquelle|url=https://clojuredocs.org/clojure.core/recur|titel=recur - clojure.core {{!}} ClojureDocs - Community-Powered Clojure Documentation and Examples|werk=clojuredocs.org|zugriff=2017-01-18}}</ref>

== 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 einander endständig aufrufen.<ref name="r5rs">{{cite journal
| author = Richard Kelsey, William Clinger, Jonathan Rees et al.
| month = August
| year = 1998
| title = Revised<sup>5</sup> Report on the Algorithmic Language Scheme
| url = https://schemers.org/Documents/Standards/R5RS/
| journal = Higher-Order and Symbolic Computation
| volume = 11
| issue = 1
| pages = 7–105
| doi = 10.1023/A:1010051815785
}}</ref><ref name="Clinger1998">William Clinger: {{Webarchiv |url=http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf |text=''Proper tail recursion and space efficiency'' |wayback=20151030113036 |archiv-bot=}} (PDF; 240 kB), Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, Juni 1998, S. 174–185</ref>

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.<ref name="eopl">Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes: ''Essentials of Programming Languages''. Second edition, MIT Press 2001, ISBN 0262062178</ref>

== Beispiele ==
Gegeben sei die rekursive Funktion ''sum'', die die Summe der ersten ''n'' [[natürliche Zahl|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 <code>sum(3)</code> 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 <code>add_sum</code> empfängt zwei Parameter <code>m</code> und <code>n</code> und liefert als Ergebnis die Summe aus <code>m</code> und der Summe der ersten <code>n</code> natürlichen Zahlen. Der Aufruf <code>add_sum (0, n)</code> liefert somit das gewünschte Ergebnis, die Summe der ersten <code>n</code> natürlichen Zahlen. Während des Ablaufs der Endrekursion in <code>add_sum</code> werden die Zwischenergebnisse im <code>m</code>-Parameter akkumuliert. In dieser endrekursiven Formulierung würde die Berechnung von <code>sum(3)</code> 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 <code>sum(n)</code> berechnete <code>sum(3)</code> als
3 + (2 + (1 + 0))
Die umgeformte Formulierung berechnet denselben Wert als
((0 + 3) + 2) + 1

Wie jede [[Primitiv-rekursive Funktion|primitiv 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 Umsetzung 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 Summenformel|Gaußsche Schulgeschichte]]“ bekannt geworden:
sum(n) = (n*(n+1)) / 2

Als Beispiel für Endrekursion mit mehreren beteiligten Funktionen hier zwei Funktionen <code>even</code> und <code>odd</code> 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:

<math>
f(x) = \begin{cases} s(x), & \mbox{falls }R(x)\\f(r(x)), & \mbox{sonst} \\ \end{cases}
</math>

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

== Siehe auch ==
* [[Platzkomplexität]]

== Einzelnachweise ==
<references />

[[Kategorie:Theoretische Informatik]]
[[pt:Recursividade (ciência da computação)#Funções recursivas em cauda]]

Endrekursion - Versionsgeschichte

imported>KlartextJan: /* Einzelnachweise Links*/