Teil 5: Schleifen und Rekursion

Um Codeteile zu wiederholen haben wir drei Möglichkeiten: Schleifen, Rekursion und Iteration über Collections mit higher-order functions. Da letztere tiefer in die Materie der funktionalen Programmierung gehen würde ich sie gerne zurückstellen und mich in diesem Artikel stattdessen auf die beiden Ersteren konzentrieren.

Da in funktionalen Sprachen unveränderlichen Objekten der Vortritt gelassen wird sind klassische Schleifen mit einem Zähler nicht gerne gesehen. Ich möchte euch zeigen wie ihr einfache Schleifen durch rekursive Methodenaufrufe ersetzt, die den Schleifen in Sachen Geschwindigkeit in nichts nachstehen.

Schleifen

Wir möchten die Zahlen von 0 bis 9 auf der Konsole ausgeben und behelfen uns dabei der while-Schleife:

var i = 0
while (i <= 9) {
  println(i)
  i += 1
}

Durch die Typeninferenz müssen wir der Variable `i` keinen Typ geben. Anzumerken sei noch, dass in Scala die Post- und Präinkrement-Statements (i++, ++i) nicht existieren. Sie würden schlicht nicht zum funktionalen Programmierparadigma passen (veränderliches Objekt). Auch in diesem Beispiel gibt es keine veränderlichen Objekte, es gibt lediglich veränderliche Variablen. Bei dem Statement `i += 1` wird nicht der Inhalt der Variable hochgezählt, es wird ein neues Integerobjekt angelegt, das daraufhin von der Variable `i` referenziert wird. Der Einfachheit halber werde ich aber dennoch von veränderlichen Objekten sprechen, vor allem weil der Scala-Compiler unnötige Objektkonstruktionen gut optimieren kann.

Es gibt ebenso eine do-while-Schleife

var i = 0
do {
  println(i)
  i += 1
} while (i <= 9)

Das war es in Scala aber auch schon was Schleifen angelangt, eine for-Schleife wie in C oder Java gibt es nicht! Es gibt lediglich eine for-Expression – diese funktioniert aber nicht wie eine normale Schleife sondern ist syntaktischer Zucker für eine Iteration über Collections.

Ein etwas komplexeres Beispiel bekommen wir wenn wir Objekte „zusammenbauen“ wollen, in unserem Fall einen String:

def str: String = {
  var i = 0
  var s = ""
  while (i <= 9) {
    s += i
    i += 1
  }
  s
}

Ich habe den Code in eine Methode gesetzt, die nur den zusammen gebauten String zurück gibt. Die runden Klammern im Methodenkopf hab ich weggelassen, da die Methode keine Seiteneffekte besitzt und uns somit bei jedem Aufruf immer wieder das gleiche Ergebnis beschert.

Rekursion

Kommen wir endlich zur Rekursion. Wir benötigen eine Methode, die wir immer wieder aufrufen können. Weiterhin benötigt diese Methode einen Parameter, nämlich die Zahl, die ausgegeben werden soll.

def loop(i: Int) {
  if (i <= 9) {
    println(i)
    loop(i+1)
  }
}

Aufgerufen wird die Methode ganz einfach mit

scala> loop(0)

Der Code ist jetzt zwar funktional, sieht aber einfach nur hässlich aus. Tja, was machen wir dagegen. Die Antwort ist, dass wir zu den Iterationen über Collections greifen müssen um „schönen“ Code zu erstellen. Da dar Scala-Compiler aber noch nicht genug optimieren kann würde das bedeuten, dass wir einen Performance-Verlust hinnehmen würden. Falls wir aber auf Performance angewiesen sind bleibt uns keine andere Möglichkeit als zu den Schleifen zu greifen. In diesem Fall würde ich sie der Rekursion sogar vorziehen, da es weniger zu schreiben wäre.

Dies ändert sich aber sobald unsere Methode Objekte „zusammenbauen“ soll:

def loop(i: Int): String =
  if (i <= 9) i+loop(i+1) else ""

Huch, was ist passiert? Plötzlich haben wir nur noch zwei Zeilen Code, es wäre sogar möglich den Methodenkörper auf die gleiche Zeile wie den Methodenkopf zu schreiben. Die Antwort ist: Alles hat einen Rückgabewert und das haben wir uns hier zu Nutze gemacht. Der ganze Overhead an geschweiften Klammern und Zeilenumbrüche kann entfallen ohne, dass wir die Lesbarkeit des Codes eingebüßt haben. Ich selbst finde kompakten Code viel lesbarer, andere mögen dies anders sehen. All jenen bleibt aber immer noch die Möglichkeit noch ein paar Zeilenumbrüche einzubauen wenn sie finden, dass der Code dann lesbarer wird.

Tail-Rekursion (Endrekursion)

Gehen wir aber ein bisschen weiter zu der Funktionsweise der Rekursion. Ich möchte nicht erklären wie Rekursion im Allgemeinen funktioniert, wer dieses Wissens noch nicht mächtig ist, den bitte ich sich das Wissen woanders anzueignen. Statt dessen möchte ich darauf hinweisen, dass das obige Beispiel nicht so effizient ist, wie das Schleifen-Beispiel, da bei jedem Rekursionsschritt die Rücksprungadresse der Methode auf dem Stack gespeichert werden muss. Um dem aus dem Weg zu gehen muss man sich Tail-Rekursion zu Nutze machen. Wenn eine Methode in der sogenannten Tail-Position ist, dann besagt dies, dass eine Methode arbeiten kann ohne über den Zustand eines anderen Rekursionsschrittes Bescheid zu wissen. Sobald das der Fall ist kommt der Scala-Compiler zum Einsatz und optimiert unsere Rekursion zu einer Schleife, d.h. wir können mit der vollen Performance der Schleife arbeiten, aber den kurzen rekursiven Code niederschreiben.

Tail-Rekursion bedeutet im Konkreten, dass wir es irgendwie schaffen müssen, dass das Objekt, das zusammengebaut werden soll in der Methode zur Verfügung steht ohne, dass wir uns den Rückgabewerte der Methode nutzen. Was könnten wir ändern um dieses Ziel zu erreichen. Es gäbe die Möglichkeit den String bereits vor dem Methodenaufruf zu definieren, aber dann müssten wir diesen innerhalb der Methode immer wieder ändern was nicht im Sinne der funktionalen Programmierung wäre.

Bleibt uns also nur noch den Wert als weiteren Parameter an die Methode zu übergeben:

def loop(i: Int, s: String): String =
  if (i <= 9) loop(i+1, s+i) else s

Aufrufen müssen wir die Methode dann mit:

scala> loop(0, "")
res51: String = 0123456789

Ob die Methode tatsächlich Tailrekursiv ist können wir mit der Annotation @tailrec herausfinden, die im Package `scala.annotation` definiert ist:

scala> import scala.annotation.tailrec
import scala.annotation.tailrec

scala> @tailrec def loop(i: Int, s: String): String =
|   if (i <= 9) loop(i+1, s+i) else s
loop: (i: Int, s: String)String

Wenn der Code ohne Fehlermeldung kompiliert, dann ist er Tailrekursiv.

Der Code ist zwar schön kurz und funktional, allerdings ist es ein wenig umständlich ihn aufzurufen. Aber auf dafür gibt es in Scala eine Lösung: `method nesting`.

Method nesting

`Method nesting` bedeutet, dass wir eine Methode innerhalb einer anderen Methode deklarieren. Ihr Gültigkeitsbereich beschränkt sich daher auf die umgebende Methode. Dies ist besonders nützlich wenn wir einen Abschnitt Code, der an einer Stelle öfters wiederholt wird nicht global zugänglich machen wollen. Ein anderer nützlicher Anwendungsfall findet sich darin, dass wir die Schnittstellen eines Objektes nach außen hin beeinflussen können. In Java hätten wir nur die Möglichkeit die betreffenden Methoden auf `private` zu setzen, so dass sie von außerhalb einer Klasse nicht weiter zugänglich sind. Dies würde aber nicht verhindern, dass die Methoden auch von innerhalb der Methode zugänglich sind, mit dem `method nesting` kann man dies hingegen schon erreichen:

def str: String = {
  def loop(i: Int, s: String): String =
    if (i <= 9) loop(i+1, s+i) else s
  loop(0, "")
}

Nach außen hin ist nur die Methode `str` zugänglich, es gibt aber keine Möglichkeit auf `loop` zuzugreifen. Dies funktioniert nicht nur bei Methoden, es wäre auch möglich `str` als `val` zu definieren – genau genommen wäre es sogar die bessere Vorgehensweise, da `str` keine Parameter erwartet und seiteneffektfrei ist und folglich eine immer identische Ausgabe produziert.

Advertisements

No comments yet

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

%d Bloggern gefällt das: