Advanced Scala – Teil 5

Advanced Scala: Tail Recursion und Optimierung

Heiko Seeberger

In der imperativen Programmierung, die im „Standard-Java“ fast ausschließlich zur Anwendung kommt, verwenden wir oft Schleifen und ändern darin den Zustand eines Objekts bzw. einer Variable. Viele Probleme lassen sich zumindest konzeptionell einfacher mit dem Prinzip der Rekursion [1] lösen. Wir wollen als Beispiel die Summenbildung über eine Liste von Int-Zahlen betrachten.

In Java könnte eine typische Implementierung folgendermaßen aussehen:

public static int sum(List numbers) {
    int result = 0;
    for (int number: numbers) {
        result += number;
    }
    return result;
}

Das können wir natürlich auch in Scala analog umsetzen:

def sum(numbers: List[Int]): Int = {
  var result = 0
  for (number 

Wie sieht nun eine rekursive Alternative aus?

def sum(numbers: List[Int]): Int = numbers match {
  case Nil => 0
  case x :: xs => x + sum(xs)
}

Zunächst fällt auf, dass diese Implementierung kürzer ist. Und wenn man sich erst einmal an die rekursive Denkweise gewöhnt hat, dann erkennt man schnell, dass dieser Weg auch einfacher zu verstehen ist. Denn „Die Summe über eine Liste ist das erste Element plus die Summe über den Rest“ entspricht viel eher dem intuitiven Verständnis als „Nimm eine Speicherzelle, iteriere über alle Elemente und addiere diese zum aktuellen Wert der Speicherzelle“.

Noch deutlicher wird der Vorteil der Rekursion bei den Fibonacci-Zahlen [2], denn diese sind ja rekursiv definiert:

fib(n) =
  0  für n = 0
  1  für n = 1
  fib(n-2) + fib(n-1)  für n > 1
Das geht noch besser!

So intuitiv und elegant Rekursionen auch sein mögen, unter der Haube sind sie nicht unproblematisch. Denn grundsätzlich wird bei jedem Aufruf ein neuer Stack Frame erzeugt, was mit Zeit und Stack-Speicherplatz verbunden ist. Gerade bei Scala ist das ein sehr ernst zu nehmendes Problem, denn der Stack ist auf der JVM typischerweise eher klein ausgelegt. Und selbst wenn wir quasi beliebig viel Stack zur Verfügung stellen, ist die Performance doch fast immer ein wichtiges Thema.

Daher ist es entscheidend, dass uns der Compiler und die Ablaufumgebung so gut wie möglich mit Optimierungen [3] unterstützt. Besonders großes Optimierungspotenzial bieten Tail Recursions bzw. Endrekursionen [4], d. h. solche rekursiven Funktionen, deren letzte Aktion zur Ermittlung des Rückgabewerts der rekursive Aufruf ist. In diesem Fall kann der Compiler die Rekursion durch eine Iteration ersetzen, sodass der Stack kein Problem mehr darstellt; eine solche Optimierung wird Tail Call Optimization genannt.

Die Java Virtual Machine lässt für Scala leider nicht alle Spielarten von Tail Call Optimizations zu. Beispielsweise ist es nicht möglich, sich wechselseitig endrekursiv aufrufende Funktionen zu optimieren. Aber natürlich werden alle Funktionen optimiert, die sich selbst endrekursiv aufrufen.

Geschrieben von
Heiko Seeberger
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.