Endrekursion (engl. Tail Call Recursion) ist eine Besonderheit bei Methoden, dass sie mit einem rekursiven Aufruf enden. Zum Einstieg: Ist die bekannte rekursive Implementierung der Fakultät endrekursiv?
int factorial(int n) {
if ( n == 0 ) return 1;
return n * factorial( n – 1 );
}
Zwar sieht es optisch so aus, als ob die factorial(int) mit einem Methodenaufruf an factorial(…) endet, doch findet hier keine Endrekursion statt, da nach dem Methodenaufruf noch eine Multiplikation stattfindet – etwas umgeschrieben ist es besser zu erkennen:
int factorial(int n) {
if ( n == 0 ) return 1;
int fac = factorial( n – 1 );
return n * fac;
}
Die Berechnung der Fakultät lässt sich umschreiben, so dass tatsächlich eine Endrekursion sattfindet, und zwar durch Einführung eines Containers für Zwischenergebnisse, genannt Akkumulator:
int factorial( int n )
{
return factorialTailrec( n, 1 );
}
private int factorialTailrec( int n, int accumulator )
{
if (n == 0) return accumulator;
return factorialTailrec( n – 1, n * accumulator );
}Die umgeschriebene Version büßt gegenüber der ursprünglichen Version an Schönheit ein. Doch endrekursive Aufrufe sind attraktiv, da eine schlaue Übersetzungseinheit sie so optimieren kann, dass der rekursive Methodenaufruf durch einen Sprung ersetzt wird. In der Java Sprache haben wir keine direkten Sprünge, doch im Bytecode schon, sodass die Basis der Optimierung im Grunde so aussehen kann:
private int factorialTailrec( int n, int accumulator ) {
start:
if ( n == 0 ) return accumulator;
accumulator *= n;
n--;
goto start;
}
Die Rekursion ist durch eine ordinäre Schleife ersetzt, was Stack einspart und eine sehr gute Performance ergibt.
In funktionalen Programmen ergeben sich eher Situationen, in denen Endrekursion vorkommt, sodass es attraktiv ist, diese zu optimieren. Die Standard-JVM kann das bisher nicht, weil Java traditionell keine funktionale Programmiersprache ist, und Endrekursion eher selten vorkommt. Zwar wird die Optimierung von Endrekursion (engl. tail call optimization) immer wieder diskutiert und auch schon in Prototypen ausprobiert, aber nie von der Oracle JVM implementiert. Für Entwickler heißt dass, rekursive Aufrufe nicht umzuschreiben in endrekursive Varianten, da sie sowieso nicht optimiert werden und nur unleserlicher würden, und bei großen Datenvolumen, sprich Stack-Tiefe, auf die übliche nicht-rekursive iterative Version umzustellen. Im Fall von factorialTailrec(..) kann dies nämlich auch vom Entwickler gemacht werden und sieht so aus:
private int factorialTailrec( int n, int accumulator ) {
while (n != 0) {
accumulator *= n;
n–;
}
return accumulator;
}
‚Scala‘ wäre eine Alternative. Der Scala-Compiler übersetzt endrekursive Funktionen zu Schleifen. Zudem gibt es eine Annotation @tailrec, bei der der Compiler dann sich beschwert, wenn die Funktion doch nicht endrekursiv ist.
Guter Artikel — kurz und verständlich.
Es hats sich jedoch ein Fehler eingeschlichen. Der gezeigte Bytecode mit dem goto würde nur für n==0 terminieren. Das Label „start:“ muss eine Zeile nach oben, also über das if, geschoben werden.
Arrrrrg, Mist! Natürlich, das Label muss höher. Danke!