Rekursion – Fluch oder Segen?

In der normalen Welt der Programmierung, also mit imperativen Sprachen wie C, C++, Java usw. findet die rekursive Programmierung selten Anwendung. Statt dessen werden Schleifen eingesetzt, um Abläufe zu wiederholen. Dieser Artikel soll eine Lanze für die Rekursion brechen, denn der resultierende Code ist elegant und ausdrucksstark.

Natürlich muss man erst mal wissen, was Rekursion überhaupt ist. Das Internetlexikon Wikipedia spricht davon, „eine Funktion durch sich selbst zu definieren“. Das hört sich jetzt erst mal abstrakt an. Das „Hello World“-Beispiel der Rekursion ist die Fakultät, d. h. die Funktion, die zu einer natürlichen Zahl n das Produkt aus 1 * 2 * 3 * ... * n berechnet. Also ist die Fakultät von 6 (auch 6! geschrieben):

6! = 1 * 2 * 3 * 4 * 5 * 6 = 720

Der imperative Java-Programmierer würde als eine Schleife verwenden, z. B.:

int fakultaet(int n) {
    int resultat = 1;
    for (i = 1; i <= 6; i++) {
        resultat = resultat * i;
    }
    return resultat;
}

Das Elegante an diesem Problem ist aber, dass die Berechnung auch anders dargestellt werden kann:

f(n) = f(n - 1) * n

Anders ausgedrückt: kennt man bereits die Fakultät von n - 1, dann braucht man diese nur mit n zu multiplizieren und hat die richtige Antwort. Natürlich ist das nur bedingt richtig, denn wenn man nicht bei 1 aufhört, setzt sich die Rekursion endlos fort. Deshalb ist es immer wichtig, ein Abbruchkriterium zu definieren. Hier also die Scala-Version der obigen Funktion:

def fakultaet(n: int) : int = 
  if (n <= 1) 1
  else n * fakultaet(n - 1);

Tipp: Obwohl Scala normalerweise sehr intelligent rät, welchen Rückgabewert eine Funktion hat, fällt es dem Compiler bei rekursiven Funktionen schwer, den korrekten Typ zu bestimmen. Deshalb hier immer den Rückgabewert angeben!

Wie immer ist die Scala-Funktion kürzer als ihr obiges (Java-)Pendant. Aber durch die Verwendung von Rekursivität finde ich den Algorithmus nun auch einfacher zu verstehen. Trotzdem ist ein gewisse Gewöhnung an die Formulierung rekursiver Algorithmen notwendig und nicht alle Schleifen müssen rekursiv dargestellt werden.

Es gibt leider auch einen Nachteil von rekursiven Funktionsaufrufen: jedes Mal werden bei einem Aufruf Werte auf den Stack gelegt. Da dieser in seiner Größe begrenzt ist, kann dies bei hohen Werten zu einem Überlauf des Stacks führen. Dies kann jedoch in der Regel vermieden werden.

Die oben dargestellt Rekursion ist linear, d. h. sie enthält nur einen rekursiven Aufruf. Von einer Endrekursion (engl. Tail Recursion) spricht man, wenn nur die letzte Anweisung einen rekursiven Aufruf enthält. Wie man den obigen Scala-Code in eine solche Endrekursion verwandelt, zeigt das folgende Beispiel:

@tailrec
def fakultaet(n: int) : int = {
  def fak(n: int, resultat: int) : int = {
    if (n <= 1) resultat
    else fak(n - 1, resultat * n);
  }
  fak(n, 1);
}

Der Vorteil einer Endrekursion liegt darin, dass man sie problemlos durch eine while-Schleife ersetzen kann. Mit Hilfe der Annotation @tailrec schafft dies der Scala-Compiler sogar ohne manuellen Eingriff, d. h. der gezeigte Code ist genauso performant wie eine Schleife.

Obwohl das gezeigte Beispiel sehr klein ausfällt, sollte die Einfachheit und Eleganz von Rekursionen dargestellt werden. In weiteren Beiträgen wird dieses Stilmittel, das insbesondere in der funktionalen Programmierung eine Rolle spielt, eingesetzt.

Beispiele:

2 Kommentare

  1. Es ist wie immer im Leben – alles hat zwei Seiten.

    Rekursion ist ein erstklassiges Mittel um bestimmte Aufgaben zu erledigen, ich denke an „mein“ Parade-Beispiel dafür: Das Suchen oder Bearbeiten von Dateien auf Speichermedien – hier ruft man doch gerne eine Funktion auf, die genau ein übergebenes Verzeichnis ausliest. Vor oder nach der Bearbeitung des Verzeichnisses wird nach Unterverzeichnissen gesucht. Wird ein Unterverzeichnis gefunden, wird sich selbst mit dem gefundenen Verzeichnis aufgerufen und das „Spielchen“ beginnt von vorne.

    Was die Stack-Größe angeht, nun, da gibt es zwei Meinungen – nämlich ob Strukturen oder Referenzen übergeben werden. Ein Stack-Überlauf bei letzteren ist im praktischen Leben eher unwahrscheinlich. Wenn doch, sollte man sowieso das Design überprüfen …

    Aber zurück zur Rekursion vs. Schleifen: Im Falle der Fakultät würde ich ehrlich gesagt noch immer die Schleife vorziehen. Das Problem an der Rekusion ist die Fehlersuche, speziell wenn es von den Daten abhängt, sprich ob es bereits der 5.196te Aufruf war, der als Objekt etwas bekommen hat, mit den die Funktion nicht klarkommt. Vor allem wenn die Logik darin komplex wird, kann die Nachvollziehbarkeit extrem darunter leiden – Na gut, Schleifen kann man auch so programmieren, die kaum einer versteht.

    Fazit: Beides hat seine Daseinsberechtigung. Es kommt einfach auf die konkrete Problemstellung an.

  2. Inzwischen kann man die Stack-Größe in der JVM ja auf astronomische Werte stellen. Trotzdem ist diese Grenze manchmal schneller erreicht, als man denkt: wenn ich die Fakultät von 5 berechne, so werden mit Rekursion 5 ganze Zahlen (a 4 Bytes) auf den Stack gepackt, also 20 Bytes – kein Problem.

    Wenn ich jedoch die Fakultät von 1.000.000.000 berechnen möchte, dann kann ich den JVM-Typ Integer nicht mehr verwenden sondern muss auf BigInteger ausweichen. Dieser braucht deutlich mehr Speicher, wieviel hängt von der Größe des Wertes ab. Aber zumindest haben wir eine 64-Bit-Referenz und sagen wir durchschnittlich 10 Bytes für die Speicherung, also 18 Bytes je Rekursionstiefe, also 18 GB! Das wird auch für moderne PCs ein Problem sein.

    Das Thema Fehlersuche ist interessant. Fehler, die bei der Rekursion eine Rolle spielen, lassen sich meistens auf logische Fehler zurückführen. Entweder breche ich die Bearbeitung zu früh ab oder ich habe vergessen, bestimmte Fälle (leeres Verzeichnis, mehr als x Einträge, Namen mit Sonderzeichen, …) zu berücksichtigen. (OK, mein schlimmster Schleifenfehler war in C – ich hatte in einer for-Schleife anstelle eines ; ein , getippt. Für die Suche brauchte ich damals – ich war jung 🙂 – 2 Tage! Inzwischen halte ich das aber für untypisch)

    Die meisten Fehler in Schleifen, die ich gesehen habe, entstanden durch falsch gesetzte Schleifenbedingungen, z. B. läuft die Schleife nicht bei 0 los oder das Abbruchkriterium ist <, hätte aber <= sein müssen. Manchmal habe ich auch einen eigenen Stil, wie die Schleife aussieht und ein anderer Programmierer mit einem anderen Stil ist dann irritiert (bei einer Korrektur seines Codes mache ich dann leichter Fehler). Auch immer gerne genommen: die Veränderung der Laufvariable im Schleifenblock, meistens als "Optimierung" gedacht. Da in Scala die Endrekursion vom Compiler in eine JVM-Code-Schleife übersetzt wird, spielt die Performance und der Speicher keine Rolle. Hier geht es nur um die Verständlichkeit des Codes. Die Rekursion steht für die Vereinfachung des Sachverhaltes auf ein leichteres Problem und damit (möglicherweise) für ein einfacheres Verständnis. Wenn man sich hieran gewöhnt, gelingen einem sehr einfache Darstellungen von Sachverhalten, die mit Schleifen komplizierter gewesen wären. Neben der Fakultät und der Summe natürlicher Zahlen ist auch die Baumsuche bzw. Bearbeitung von Bäumen oder anderen Datenstrukturen mit rekursiven Ansätzen meistens einfacher. Aktuell arbeite ich z. B. an Splay-Trees (auch hierzu ein eigener Artikel), bei denen die Suche sehr einfach rekursiv dargestellt werden kann. Besonders in der funktionalen Programmierung lassen sich mit Rekursion und Verkettung von Funktionen (dazu später mal ein eigener Beitrag) sehr elegant komplexe Abläufe darstellen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.