... & Kontext: Rekursion

"Konsole & Kontext" ist eine gemeinsame Serie von Golo Roden und Michael Wiedeking, in der sich die beiden regelmäßig mit Konzepten der (funktionalen) Programmierung beschäftigen. Während "Konsole & …" die praktische Anwendung dieser Konzepte in JavaScript und Node.js zeigt, erläutert "… & Kontext" deren jeweiligen eher theoretischen Hintergrund.

Zu den ersten Dingen, mit denen man im Zusammenhang mit dem Programmieren konfrontiert wird, gehört die Rekursion. Typischerweise wird diese über die Fakultätsfunktion, die Fibonacci-Zahlen oder den Turm Hanoi eingeführt – also Dinge, die man in seiner täglichen Arbeit praktisch nie braucht. Aber wenn man mal ehrlich ist, gibt es dafür auch keine ernstzunehmenden Alternativen.

Mit der Fakultätsfunktion lässt sich etwa die Anzahl der Möglichkeiten bestimmen, auf wie viele Arten sich n Personen in einen Raum mit n Stühlen setzen können. Der Erste kann sich einen der n Stühle aussuchen. Für den Zweiten verbleiben dann nur noch n – 1 Möglichkeiten. Das geht so lange weiter, bis zum Letzten, der leider nur noch den verbleibenden Stuhl nehmen kann. Damit haben die n Leute

n · (n – 1) · (n – 2) · … · 2 · 1

Möglichkeiten, sich in den Raum zu setzen.

Die Mathematiker schreiben dafür n! und definieren die Funktion rekursiv, indem sie definieren:

1! = 1
n! = n · (n – 1)!

Wie man sieht, wird die Fakultät mit sich selbst definiert. Damit diese auch wirklich ein Ergebnis liefert und nicht ewig sich selbst aufruft, muss es mindestens eine Zuordnung zu konkreten Werten geben. Die Rolle übernimmt hier die 1, indem der Wert von 1! entsprechend festgelegt wird. (Das 0! gelegentlich auch definiert wird und meist den Wert 1 zugeordnet bekommt, hat praktische Gründe; soll uns aber an dieser Stelle nicht interessieren.)

In C-orientierten Sprachen würde man die Fakultätsfunktion (für Zahlen positive Zahlen) in etwa wie folgt definieren:

  int fac(int n) {
    if (n <= 1) {
      return 1;
    } else {
      return n * fac(n – 1);
    }
  }

An dieser Stelle sei noch erwähnt, dass die Fakultätsfunktion sehr schnell wächst und schon 17! zu einem Überlauf führt. Ein long macht da auch keinen viel besseren Job, denn schon 21! sprengt dessen Rahmen.

Man kann über die Rekursion ja sagen, was man will, aber sie macht viele Dinge sehr viel einfacher. Wer das nicht glaubt, der kann ja mal versuchen, die Fakultätsfunktion binnen einer Minute fehlerfrei iterativ zu programmieren. Wer sagt, dass das kein Problem ist, der programmiere bitte innerhalb von weiteren fünf Minuten den Turm von Hanoi – natürlich auch iterativ.

Leider sagt man über die Rekursion auch, dass sie zu langsam sei. Das ist aber nur bedingt richtig, denn oftmals reicht die Performanz von dem, was man rekursiv programmiert, völlig aus. Dennoch gilt es, die am Nanosekundensyndrom leidenden Programmierer vom Gegenteil zu überzeugen. Und das gelingt ganz einfach, wenn die rekursive Funktion bestimmte Eigenschaften mitbringt.

Obige Implementierung lässt sich nämlich auch anders schreiben, wenngleich das nicht mehr ganz so intuitiv ist. Man bedient sich dabei eines Akkumulators, der das Ergebnis "einsammelt".

  int fac(int akku, int n) {
    if (n <= 1) {
      return akku;
    } else {
      return fac(n * akku, n – 1);
    }
  }

Der Unterschied zur ursprünglichen Funktion ist gar nicht so groß, insbesondere ist das Abbruchkriterium immer noch dasselbe. Der Einsatz des Akkumulators hat aber den Vorteil, dass die Multiplikation nicht mehr "alleine" dasteht, sondern über einen Parameter dem rekursiven Aufruf verfügbar gemacht wird. Natürlich soll die ursprüngliche Funktionssignatur unverändert bleiben, also muss die Implementierung entsprechend angepasst werden.

  int fac(int n) {
    return fac(1, n);
  }

Wenn möglich würde man die intern benötigte Funktion auch lokal definieren, aber das ist bei den meisten C-orientierten Sprachen leider nicht möglich.

Aber was hat man nun davon, die Funktion derart umzustellen? Na ja, man muss sie nicht mehr aufrufen! Wenn nämlich in einer rekursiven Funktion die letzte Anweisung der Aufruf dieser rekursiven Funktion ist, kann man auf den eigentlichen Aufruf verzichten und ihn – nach Aktualisierung der Parameter – durch einen einfachen Sprung ersetzen.

  int fac(int akku, int n) {
    label:
      if (n <= 1) {
        return akku;
      } else {
        akku = n * akku;
        n = n – 1;
        goto label;
      }
  }

Und das entspricht etwa dem, was ein Programmierer macht, wenn er die Fakultät iterativ implementieren will. Natürlich bedient man sich dann etwas gesellschaftsfähigeren Mechanismen, wie einer Schleife.

  int fac(int n) {
    int akku = 1;
    while (n > 1) {
      akku = n * akku;
      n = n – 1;
    }
    return akku;
  }

Diese Endrekursion unterstützen die meisten funktionalen Programmiersprachen. Bei den imperativen Sprachen, wie den C-orientierten, tut man sich – wie der Name schon vermuten lässt – etwas schwerer. Denn warum soll man dem Compiler etwas überlassen, was man auch von Hand machen kann? ()