Rekursionen – Programmieren lernen mit JavaScript – Thytos
Nächstes Video startet in 3 Sekunden.
Programmieren lernen mit JavaScript

Rekursionen

Re­kur­sio­nen sind Funk­tion­en, die sich selbst auf­ru­fen. Sie sind ein mäch­ti­ges Werk­zeug, kön­nen je­doch un­vor­sich­tig ein­ge­setzt außer Kon­trol­le ge­ra­ten.

Eine Rekursion (aus dem Lateinischen von recurrere, zurücklaufen) tritt auf, wenn etwas in seiner Definition auf sich selbst verweist. In der Programmierung bezieht es sich auf Funktionen, die sich selbst aufrufen.


Die Droste Kakao Dose zeigt eine Frau, die eine Droste Kakao Dose hält, die eine Frau zeigt, die eine Droste Kakao Dose hält.
Die Droste Kakao Dose von 1904 ist eine rekursive Illustration, die als Droste Effekt bekannt wurde.

Mit Rekursionen kann in der Programmierung sehr viel erreicht werden. Allerdings können sie auch den Computer lahmlegen, wenn sie unvorsichtig eingesetzt werden.

Die folgende Funktion countdown gibt eine Zahl in einem Dialogfenster aus. Wird das Fenster geschlossen, erscheint das nächste mit der nächstkleineren Zahl. So werden die Zahlen heruntergezählt.

// ACHTUNG: Dieses Beispiel so nicht nachmachen

function countdown(nr) {
  alert(nr);
  countdown(nr - 1); // Rekursion & Herunterzählen
}

countdown(10); // Start bei 10

Umgesetzt wird das durch eine Rekursion: countdown ruft sich selbst mit der nächstkleineren Zahl auf.
Wird die Funktion ausgeführt, scheint anfangs auch alles richtig zu funktionieren – bis zu dem Punkt, an dem der Countdown vorbei sein sollte. Statt bei 1 oder 0 aufzuhören, wird weiter heruntergezählt. -1, -2, -3, etc. sollen nicht Teil des Countdowns sein.

Abbruchbedingung

Das entscheidende Kriterium, um Rekursionen sinnvoll einzusetzen, ist das Einführen einer Abbruchbedingung, im Englischen break condition. Solange nicht klar ist, wann die Funktion stoppen soll, sich selbst aufzurufen, wird sie dies endlos weiter tun, bis der Prozess von außen beendet wird.

Umgesetzt wird das üblicherweise durch eine if-Bedingung. Im Fall der countdown-Funktion soll die Funktion abbrechen, bevor in den Minusbereich gezählt wird. Eine Abbruchbedingung kann auf unterschiedliche Art implementiert werden.

// Beispiel 1: Alles durch if bedingt
function countdown(nr) {
  if (nr >= 0) {
    alert(nr);
    countdown(nr - 1);
  }
}

// Beispiel 2: Nur der rekursive Aufruf durch if bedingt
function countdown(nr) {
  alert(nr);
  if (nr > 0) countdown(nr - 1);
}

// Beispiel 3: Durch return aus Funktion herausgehen
function countdown(nr) {
  if (nr < 0) return;
  alert(nr);
  countdown(nr - 1);
}

Geltungsbereich (Function scope)

Im folgenden Beispiel werden zwei Variablen erstellt: Eine außerhalb und eine innerhalb einer Funktion. Anschließend wird die Funktion ausgeführt. Die Variable, die außerhalb definiert wurde, steht anschließend noch immer zur Verfügung; die Variable, die innerhalb der Funktion definiert wurde, dagegen nicht.

var a = 5;
function beispiel() {
  var b = 6;
}
beispiel(); // Funktion ausführen
a;
// => 5
b;
// Uncaught ReferenceError: b is not defined

Funktionen kreieren ihren eigenen Geltungsbereich, im Englischen Function scope. Das bedeutet, dass Variablen und andere Werte, die in einer Funktion erstellt werden, auch nur innerhalb dieser Funktion gelten und zur Verfügung stehen.
Deswegen ist die Variable b nicht außerhalb der Funktion zu erreichen und es gibt einen ReferenceError, einen Referenz-Fehler, weil b außerhalb nicht definiert ist.

Andersherum funktioniert das dagegen schon: Auf Variablen, die außerhalb einer Funktion definiert sind, kann auch innerhalb der Funktion zugegriffen werden.

var a = 5;
function beispiel() {
  a + a; // Zugriff auf äußere Variable
}
beispiel();

Wie kann eine Funktion dann aber Werte, die sie ermittelt, wieder nach außen weiterreichen? Es gibt zwei Möglichkeiten.

Zum einen kann der Zugriff auf den äußeren Scope zunutze gemacht werden. Eine Variable, die das Ergebnis einer Funktion enthalten soll, kann außerhalb dieser definiert werden. Wenn die Funktion ausgeführt wird, schreibt sie einen Wert in diese Variable.

var ergebnis; // Variable im äußeren Scope deklarieren
function addiere(nr) {
  // Zugriff auf die äußere Variable innerhalb der Funktion
  ergebnis = nr + nr;
}
addiere(5);
ergebnis;
// => 10

Die zweite und bessere Möglichkeit ist die Nutzung des return-Statements.

function addiere(nr) {
  return nr + nr;
}
addiere(5);
// => 10

Wert zurückgeben (return)

Eine return-Anweisung in einer Funktion erzielt zwei Sachen:

  • Die Ausführung der Funktion wird mit dem Aufruf der return-Anweisung beendet. Code, der nach dem return folgt, wird nicht weiter ausgeführt. Nach der Beendigung der Funktion wird der aufrufende Code weiter ausgeführt.
  • Ein Wert, der hinter dem return-Statement steht, wird an die aufrufende Funktion zurückgegeben. In JavaScript wird undefined zurückgegeben, wenn kein Wert hinter return angegeben ist.

Die folgende Funktion rechnet Zweierpotenzen mit Hilfe einer Rekursion aus. Es funktioniert folgendermaßen:

  • Alles hoch null ergibt eins. Auch 2⁰ ergibt 1. Entsprechend soll die Funktion 1 zurückgeben, wenn der Exponent 0 ist.
    function zweiHoch(exp) {
      if (exp === 0) {
        return 1;
      }
    }
    
  • Ist der Exponent größer als 0 soll 2 so oft miteinander multipliziert werden, wie der Exponent groß ist. Das passiert hier rekursiv: Der Exponent wird heruntergezählt, indem zweiHoch mit dem nächstkleineren Exponenten aufgerufen wird.
    function zweiHoch(exp) {
      if (exp === 0) {
        return 1;
      } else if (exp > 0) {
        return 2 * zweiHoch(exp - 1);
      }
    }
    

Probiert die Funktion in der Konsole aus und ihr werdet sehen, dass sie die korrekten Zweierpotenzen zurückgibt.

zweiHoch(2)
// => 4

zweiHoch(3)
// => 8

zweiHoch(10)
// => 1024

Falls ihr noch nicht vollständig verstanden habt, warum das funktioniert, folgt hier eine Schritt für Schritt Beschreibung, was passiert. Die Einrückungen stellen dabei die Tiefe des Callstacks dar.

  1. Als Exponent wird beispielhaft 2 genommen und somit zweiHoch(2) aufgerufen.
    1. Die erste if-Bedingung wird überprüft, aber da exp nicht 0 ist, übersprungen.
      if (2 === 0) { …
      
    2. Die zweite if-Bedingung wird überprüft, und da exp größer 0 ist, ausgeführt.
      if (2 > 0) { …
      
    3. Es wird 2 * zweiHoch(exp - 1) ausgeführt, das heißt 2 * zweiHoch(2 - 1) und somit 2 * zweiHoch(1).
      return 2 * zweiHoch(2 - 1); // => return 2 * zweiHoch(1);
      
    4. Um das zu errechnen, wird zweiHoch(1) aufgerufen.
      1. Die erste if-Bedingung wird überprüft, aber da exp nicht 0ist, übersprungen.
      2. Die zweite if-Bedingung wird überprüft, und da exp größer 0 ist, ausgeführt.
      3. Es wird 2 * zweiHoch(exp - 1) ausgeführt, das heißt 2 * zweiHoch(1 - 1) und somit 2 * zweiHoch(0).
      4. Um das zu errechnen, wird zweiHoch(0) aufgerufen.
        1. Die erste if-Bedingung wird überprüft, und da exp gleich 0 ist, ausgeführt.
        2. Die Funktion wird mit return 1; beendet und der Wert 1 an die aufrufende Funktion zurückgegeben.
      5. zweiHoch(0) hat 1 zurückgegeben. Damit kann die Rechnung 2 * zweiHoch(exp - 1) gelöst werden, denn es ist 2 * 1, also 2. Dieser Wert wird durch return an die aufrufende Funktion zurückgegeben.
        return 2 * zweiHoch(0); // => return 2 * 1;
        
    5. zweiHoch(1) hat 2 zurückgegeben. Damit kann die Rechnung 2 * zweiHoch(exp - 1) gelöst werden, denn es ist 2 * 2, also 4. Dieser Wert wird durch return an die aufrufende Funktion zurückgegeben.
      return 2 * zweiHoch(1); // => return 2 * 2;
      
  2. Die Funktion zweiHoch(2) hat 4 zurückgegeben.

Dieses Beispiel nutzt die Möglichkeiten von Rekursionen, macht sie mit einer Abbruchbedingung kontrollierbar und schöpft mit dem return-Statement das volle Potential aus.

Beispielfall: Rekursion ohne Abbruchbedingung

In dieser Funktion, die am Ende des letzten Artikels dieser Serie vorkam, fehlt eine Abbruchbedingung, weshalb sie eine Fehlermeldung wirft.

function zeigeZeichen(str, i) {
  if (isNaN(i)) {
    i = 0;
  }
  if (str) {
    alert("Das " + (i+1) + ". Zeichen ist ein " + str[i]);
    zeigeZeichen(str, i - 1);
  }
}

Öffnet die Konsole in eurem Browser und überlegt, wie ihr den Code verändern müsstet, um die Rekursion an der gewünschten Stelle abzubrechen. Lest erst weiter, wenn ihr selbst eine Lösung gefunden habt.

Es gibt wie bei den meisten Problemen in der Informatik verschiedene Möglichkeiten, sie zu lösen. Falls ihr eine Lösung gefunden habt, die nicht im Folgenden aufgeführt ist, sagt das nichts über die Qualität eures Lösungswegs aus.

Eine Möglichkeit ist, die Funktion mit return abzubrechen, wenn i länger ist als der String. Die Länge des Strings kann über die length-Property ausgelesen werden.

function zeigeZeichen(str, i) {
  if (isNaN(i)) {
    i = 0;
  }
  if (i >= str.length) {
    // i ist größer als die Länge des Strings
    // Hier gibt es keine Buchstaben mehr, die ausgelesen werden können
    return; // <= Breche ab
  }
  …
}

Eine andere Möglichkeit ist, den rekursiven Aufruf von einer Bedingung abhängig zu machen. Tatsächlich ist das bereits der Fall, denn der Aufruf befindet sich innerhalb von if (str) …. Diese Bedingung kann mit Hilfe einer logischen UND-Verknüpfung erweitert werden.

function zeigeZeichen(str, i) {
  …
  if (str && i < str.length) {
    …
    // Führe den rekursiven Aufruf nur aus, wenn i < str.length
    zeigeZeichen(str, i - 1);
  }
}

Statt über die Länge des Strings zu gehen, kann die Bedingung sich auch zunutze machen, dass der Wert undefined falsy ist. Wird eine Stelle im String ausgelesen, an der es keine Zeichen gibt, ist der Wert undefined.

function zeigeZeichen(str, i) {
  …
  // Falls i > str.length, ist str[i] undefined
  // undefined ist ein falsy Wert, sodass die Bedingung nicht erfüllt ist
  if (str && str[i]) {
    …
  }
}

Das zeigt, dass es ganz unterschiedliche Arten gibt, wie eine Abbruchbedingung implementiert werden kann.