Tail Recursion
Endrekursion ist Rekursion, bei der der rekursive Aufruf die letzte Operation der Funktion ist; Compiler können sie zu einer Schleife optimieren und so einen Stacküberlauf vermeiden.
Zweck
Schleifenlogik rekursiv ausdrücken, ohne den Stack wachsen zu lassen — ein Kernstück funktionaler Sprachen.
Mechanismus
Steht der rekursive Aufruf in Endposition (letzte Operation vor dem Return), verwandelt ihn die TCO in einen Sprung statt eines Aufrufs und nutzt den Stack-Frame wieder. Dafür ist Sprachsupport nötig (in Scheme/SML verpflichtend; im JS-Strict-Modus laut Spezifikation optional, aber nur Safari/JavaScriptCore implementiert es). Nicht-endständige Rekursion muss mit einem Akkumulator umgeschrieben werden.
Anwendungsfälle
- Funktionale Programmierung
- Vermeidung von Stacküberläufen
- Rekursoptimierung