Endrekursion


Ich musste erst mal Tante Wikipedia fragen, wie man „tail recursion“ in vernünftiges Deutsch übersetzt – „Schwanzrekursion“ schien mir irgendwie nicht ganz passend zu sein. Was Rekursion ist, sollte eigentlich jeder Programmierer wissen (falls nicht, wird es gut im 2. Kapitel dieses Skripts erklärt), aber „Endrekursion“ dürfte für die meisten Java-Programmierer ein Fremdwort sein. In Scala, wo Rekursion der Normalfall und Schleifen eher die Ausnahme sind, gehört dieses Konzept zum grundlegenden Rüstzeug – aber keine Angst, es ist wirklich nicht kompliziert.

Schauen wir uns zwei verschiedene Implementierungsvarianten für die Fakultät an:

//Variante 1 - nicht endrekursiv
def fac1(n:Int):BigInt = 
  if (n <= 1) 1
  else fac1(n-1) * n

fac1(20)
//--> res0: BigInt = 2432902008176640000

//Variante 2 - endrekursiv
def fac2(n:Int):BigInt = {
  def loop(k:Int, prod:BigInt):BigInt = 
     if (k <= 1) prod 
     else loop(k-1, prod * k)
 
  if (n <= 1) 1 else loop(n,1) 
}

fac2(20)
//--> res1: BigInt = 2432902008176640000

Schön, zumindest kommt bei beiden das gleiche Ergebnis heraus. Variante 1 sieht kürzer, hübscher und verständlicher aus, Variante 2 ist der Stil, den man gewöhnlich in Scala findet. Warum? Weil die erste Version nicht nur langsamer ist, sondern sogar zu Stack-Überläufen führen kann, während das bei Variante 2 nicht vorkommen kann.

Variante 1 hat nämlich das Problem, dass die Rechnung noch nicht „fertig“ ist, wenn der rekursive Aufruf erfolgt. So wird der Aufruf von fac1(5) als ((((1*2)*3)*4)*5) ausgeführt. Die Rekursion steigt tiefer und tiefer ab, und am Ende liefert sie die Ergebnisse jeweils dem darüberliegenden Aufruf zurück. Dieser führt noch eine Multiplikation aus und gibt seinerseits das Ergebnis nach „oben“ weiter.

Variante 2 dagegen lagert die Rekursion in eine innere Methode loop aus, die ein zusätzliches Argument – nämlich das Produkt der bisherigen Werte – besitzt. Durch diesen Trick ist der rekursive Aufruf das allerletzte, was in loop passiert. Aus diesem Grund braucht man die gerade abgegearbeitete Version des Aufrufs nicht mehr, sie ist für die weitere Berechnung nicht mehr nötig, und kann sozusagen (nach einer Neubelegung der Argumente) „recycelt“ werden. Und genau das tut die JVM (allerdings nicht so raffiniert, wie das funktionale Compiler tun): sie steigt nicht eine Ebene „tiefer“, sondern verwendet die aktuelle Umgebung von loop erneut, ohne dass ein echter Methodenaufruf stattfinden würde. Der generierte Byte-Code ähnelt dann mehr einer while-Schleife als dem von Variante 1, und ist entsprechend effizient. Diese Optimierung nennt sich Endrekursion.

Es gibt also einen guten Grund dafür, Variante 2 zu bevorzugen, auch wenn sie ein wenig komplizierter ist. Es lohnt sich, etwas Gehirnschmalz zu investieren, um seine Methoden endrekursiv zu formulieren – mit etwas Übung ist das gar kein Problem. Manchmal reicht schon eine andere Berechnungsreihenfolge, aber oft muss man auch auf den Trick mit dem „Sammelparameter“ (der offizielle Name ist „Akkumulator“ oder kurz „accu“) zurückgreifen.

In Scala 2.8 gibt es übrigens eine Annotation namens @tailrec, bei der der Compiler eine Warnung ausgibt, wenn die entsprechende Methode nicht so übersetzt werden kann, dass sie endrekursiv ausgeführt wird – eine großartige Hilfe, um Performanceprobleme und Stacküberläufe zu vermeiden.

Da Endrekursion eine Optimierungstechnik der JVM und nicht des verwendeten Compilers ist, gelten alle Ausführungen auch für Java. Wenn man also in Java einen Stacküberlauf durch Rekursion bekommt, kann man die betroffene Methode genauso in der hier präsentierten Weise umformulieren, um Endrekursion zu ermöglichen.
… dachte ich zumindest, bin aber eines besseren belehrt worden. Es ist der Scala-Compiler und nicht die JVM, der die Endrekursions-Optimierung vornimmt. Später mehr dazu.

Dann wünsche ich euch noch fröhliches Rekursieren!

Advertisements

7 Gedanken zu “Endrekursion

  1. Welche JVM führt die Endrekursions-Optimierung durch? Hast Du da Quellen?

    Folgende Methode gibt z.B. nach 6000 mit StackOverflowError auf (JRE 1.6.0_10).

    public static final void recursive(int i) {
    if (i%1000 == 0) System.out.println(i);
    recursive(i+1);
    }

    Mein bisheriger Eindruck ist, dass die Optimierung eine Eigenschaft des Scala-Compilers ist, nur unter ganz bestimmten Bedingungen zum Zug kommt (daher @tailrec) und zur Zeit nicht auf Java übertragen werden kann.

  2. Ja, die tail call optimization ist ein Feature des Scala-Compilers. Das kann man gut sehen, wenn man den Bytecode disassambled. Java würde die Methode neu aufrufen, während Scala an den Anfang der Methode zurückspringt.

    In Martins Beispiel könnte man statt System.out.println eine Exception werfen. Dann würde man im Stacktrace die Methodenaufrufe sehen, in der Scala Variante wäre das nicht so.

  3. Danke wollte schon meine Scala Umgebung hochfahren um die Antwort auf die Endrekursion zu ermitteln, da ich bei Scheme über diesen Begriff gestolpert bin.

    Gruß JJR

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s