Programmierkonzepte, Teil 3: Rekursion

Die Rekursion ist eines der grundlegenden Konzepte in Mathematik und Informatik. Dennoch gibt es Programmiersprachen, die die Rekursion nicht oder nur bedingt unterstützen.

Das Produkt der natürlichen Zahlen von 1 bis n wird als n! bezeichnet. Die mathematische Funktion, die den Wert von n! berechnet, heißt Fakultät (im Englischen: factorial) und lässt sich iterativ, zum Beispiel in JavaScript, implementieren:

'use strict';

const factorial = function (n) {
  let result = 1;

  for (let i = 2; i <= n; i++) {
    result *= i;
  }

  return result;
};

console.log(factorial(5)); // => 120

Der Code lässt sich allerdings auch rekursiv schreiben, sodass die Berechnung von n! auf die Berechnung von (n-1)! zurückgeführt wird:

'use strict';

const factorial = function (n) {
  if (n <= 1) {
    return 1;
  }

  return n * factorial(n - 1);
};

console.log(factorial(5)); // => 120

Mehr Infos

Programmierkonzepte

• Teil 1: Bedingungen
• Teil 2: Funktionen höherer Ordnung
• Teil 3: Rekursion
  

Die rekursive Implementierung ist nicht nur kürzer, sondern auch besser verständlich, da der Zusammenhang zwischen dem Wert n! und dessen Vorgänger (n-1)! auf dem Weg besser ersichtlich wird. Das ist jedoch nicht in jeder Programmiersprache möglich: So unterstützte beispielsweise die 1957 erschienene Sprache Fortran zunächst keine Rekursion.

Glücklicherweise schränkt der Verzicht auf Rekursion die Anzahl der potenziell möglichen Programme nicht ein: Alles, was sich rekursiv ausdrücken lässt, kann man auch iterativ formulieren – und umgekehrt. Das ändert jedoch nichts an der Tatsache, dass sich einige Probleme auf Grund ihrer Natur rekursiv geschickter formulieren lassen als iterativ.

Ein besonderes Problem der Rekursion ist der Speicherverbrauch: Im Gegensatz zur Iteration, die mit einer begrenzten Menge an Speicher auskommt, benötigt die Rekursion für jeden Schritt mehr Speicher. Das liegt am zusätzlichen Funktionsaufruf und dem Speichern der Parameter auf dem Stack. Nahezu allen Entwicklern dürfte in dem Zusammenhang bereits ein Stack-Overflow begegnet sein: Die Rekursion wird in dem Fall so tief, dass dem Prozess der Speicher ausgeht.

Das lässt sich gegebenenfalls durch das Konzept der Endrekursion vermeiden, was aber nicht alle Sprachen unterstützen. Die Endrekursion ermöglicht, einen Algorithmus rekursiv zu formulieren, ihn aber während der Ausführung durch eine gleichwertige Iteration zu ersetzen: Auf dem Weg lässt sich der Stack Overflow vermeiden. Dazu ist es erforderlich, dass die letzte Anweisung der rekursiven Funktion dem rekursiven Aufruf der Funktion entspricht:

'use strict';

const factorialInternal = function (n, accumulator) {
  if (n <= 1) {
    return accumulator;
  }

  return factorialInternal(n - 1, n * accumulator);
};

const factorial = function (n) {
  return factorialInternal(n, 1);
};

console.log(5); // => 120

Die Laufzeitumgebung beziehungsweise der Compiler können den endrekursiven Aufruf in eine Schleife umwandeln, wodurch der Stack nicht weiter anwächst (JavaScript unterstützt Endrekursion seit ES2015). Da zugleich auch die rekursiven Funktionsaufrufe entfallen, ist ein Algorithmus, der endrekursiv formuliert ist, zumeist auch effizienter in der Laufzeit.

Einige Sprachen wie F# und OCaml unterstützen Rekursion zwar, man muss sie jedoch explizit anfordern. In F# beispielsweise dient dazu das Schlüsselwort rec: Fehlt es bei der Definition einer Funktion, ist es für sie nicht möglich, sich selbst aufzurufen. Der Beitrag "Why are functions in Ocaml/F# not recursive by default?" auf Stack Overflow nennt als primären Grund dafür, dass es auf dem Weg möglich ist, Funktionen neu zu definieren, ohne die Zugriffsmöglichkeit auf die ursprüngliche Funktion zu verlieren:

"Functions are not recursive by default in the French CAML family of languages (including OCaml). This choice makes it easy to supercede function (and variable) definitions using let in those languages because you can refer to the previous definition inside the body of a new definition. F# inherited this syntax from OCaml."

Wie auch bei logischen Bedingungen und Funktionen höherer Ordnung war Lisp die erste Sprache mit Unterstützung für Rekursion. Die Funktion zur Berechnung der Fakultät lässt sich dort sehr kompakt wie folgt definieren:

(defun factorial (n)
  (if (<= n 1)
    1
    (* n (factorial (1- n)))))

(factorial 5) ; => 120

tl;dr: Rekursion ist für die Ausdrucksstärke einer Programmiersprache nicht zwingend notwendig, verbessert aber gelegentlich die Lesbarkeit von Code. Das Konzept der Endrekursion vermeidet zudem Probleme mit dem Speicher und der Leistung. Die erste Sprache mit Unterstützung für Rekursion war Lisp. ()