Rekursive Funktionen in Javascript

Rekursionen anstelle von while-Schleifen

Rekursionen wiederholen Anweisungen in einer immer wieder gleichen Art und Weise. Javascript nutzt Rekursionen für Animationen mit requestAnimationFrame und setInterval, für das Sortieren von Arrays und für Loops durch verschachtelte Baumstrukturen. Rekursive Funktionen werden meist mit mathematisch interessanten Beispielen bestückt, so dass viele Entwickler Rekursionen eher für ein Thema am Rande ansehen, das fürs Scripting in Webseiten irrelevant ist. Dabei sind rekursive Funktionen eine Alternative zu while-Schleifen und for-loops und fast immer einfacher, verständlicher und effizienter. So z.B. ein Countdown:

const countDown = x => {
   if (x < 0) return; // Bedingung für den Abbruch
   console.log (x);
   countDown (x-1);
}

countDown (10);

Hier erlaubt die Rekursion, dass der Benutzer beliebig viele Felder erzeugt, um den Mittelwert einer Zahlenreihe zu berechnen.

function newField() {
   document.getElementById('wert').addEventListener("focus", function getFocus() {
      let newInput = this.cloneNode(true);
      this.parentNode.appendChild(newInput);
      this.removeAttribute("id");
      this.removeEventListener("focus", getFocus);
      newField();
   });
}

newField();

Wie lang oder wie oft die Rekursion durchgeführt wird, muss innerhalb der Funktion gesteuert werden: Damit die Rekursion endet, braucht sie eine Bedingung und darf beim Eintreffen nicht erneut aufgerufen werden. Ansonsten kommt die große unendliche Schleife …

Hier ist der Abbruch einfach: Die Rekursion wird nur ausgeführt, wenn der Benutzer ein Feld anklickt, um den nächsten Wert einzugeben.

To understand recursion, one must first understand recursion.

—Stephen Hawking

Verschachtelte Listen

Das DOM – Document Object Model – ist eine verschachtelte Baumstruktur und zu den Klassikern gehören die verschachtelten Navigationsmenüs.

const tree = [
  {
    'name': 'name1',
    'tree': [
      {'name': 'name2'},
      {'name': 'name3'},
      {
        'name': 'name4',
        'tree': [
          {'name': 'name5'},
          {'name': 'name6'}
        ]
      },
      {'name': 'name7'}
    ]
  },
  {
    'name': 'name8',
    'tree': [
      {'name': 'name9'}
    ]
  }
];

// Elemente aus einem tief verschachtelten JSON-Array auslesen
var buildTree = function(tree) {
   tree.forEach (function(item) {
      document.querySelector(".list").textContent += item.name + " ";
      if(item.tree) buildTree(item.tree);
   });
}
buildTree(tree);

Wenn die Daten nicht linear, sondern strukturiert und ebenso tief verschachtelt ausgegeben werden sollen, wird es einen Tick länger.

let buildTree = function (tree, container) {
  tree.forEach (function (item) {
    let newContainer = document.createElement('div');
    newContainer.textContent = item.name;

    container.appendChild(newContainer);
    if (item.tree) buildTree (item.tree, newContainer);
  });
}

buildTree (tree, document.querySelector(".struct"));

Verschachtelte Liste zu JSON

JSON wird meist als String vom Server zum Browser übertragen, z.B. um Informationen zu Produkten ohne jeglichen Overhead zu übertragen. Das Script im Browser entwickelt dann die HTML-Struktur aus den JSON-Daten.

Wenn die Daten hingegen auf der Webseite in einer verschachtelten Liste vorliegen (z.B. hierarchische Stichwörter zu Bildern), müssen die Daten in ein JSON-Objekt oder -Array übernommen werden. Wenn die Tiefe der Liste nicht begrenzt ist, ist eine Rekursion die Lösung.

• Architektur
• Computer
  • Icon
  • Pattern
  • Button
• Fahrzeug
• Kamera
  • Histogramm
  • Weißableich
    • Auto
    • Sonne
    • Bewölkt
  • Sensor
• Landschaft
  • Gebirge
  • Strand

function FetchChild(){
   let data =[];
   let list = document.querySelectorAll("#lightroom > li");
   document.querySelectorAll("#lightroom > li").forEach ( elem => {
      data.push ( vanillaJSON ( elem ) );
   });
   return data;
}
  
function vanillaJSON (li) {
   // liest den ersten Node (Text) aus li
   let subObj = { "name": li.childNodes[0].textContent.trim() };
   
   // Prüft, ob das li nach dem Text ein ul enthält
   if (li.querySelector("ul")) {
      [...li.querySelector("ul").children].forEach ( item => {
         if (!subObj.children) { subObj.children = []; }
         subObj.children.push(vanillaJSON(item));
      });
   } 
   return subObj;
}

const obj = FetchChild();

const pre = document.querySelector ("pre.result");
pre.textContent = JSON.stringify(obj, null, 2);

FetchChild liest die li-Elemente der ersten Ebene ein und ruft für jedes li-Element vanillaJSON auf. Wenn ein li-Elemente eine weitere Liste ul enthält, ruft sich die Funktion vanillaJSON selber rekursiv auf.

Für IE11 liegen die Hürden zu hoch: IE11 unterstützt weder forEach noch den spread-Operator [...li.querySelector("ul").children].

Selbstausführende rekursive Funktionen

Anstelle der gradlinigen Funktion sieht man rekursive Funktionen in Javascript häufig als Funktionsaufruf oder function expression oder sofort ausgeführte anonyme Funktion oder self invoking function. Das macht die Rekursion deutlicher und im Quelltext besser nachvollziehbar.

let result = (function computeFactorial (number) {
   if (number <= 1) {
      return 1;
   }
   return number * computeFactorial (number - 1 );
} (5) );

console.log ('Result ' + result);

Man beachte die runden Klammern rund um die komplette Funktion!

Rekursive anonyme Funktionen

Wer das Konzept der anonymen Funktionen mag, fragt sich jetzt natürlich sofort, ob und wie anonyme Funktion rekursiv aufgerufen werden, da sie ja keinen Namen haben.

In jeder Funktion existiert ein Arguments-Objekt, das neben der bekannten Eigenschaft length die selten benutzte Eigenschaft callee hat. callee gibt den Funktionskörper der aktuell ausgeführten Funktion zurück. Anonyme Funktionen verwenden die callee-Eigenschaft des Arguments-Objekts, um sich selber rekursiv aufzurufen.

Das Argument callee wurde allerdings aus dem ECMASCRIPT 5 Strict Mode entfernt.

<form action="rekursive-Funktionen.html" method="get" id="jsfuncCallee">
   <p><input type="text" name="mittel" id="mit0"></p>
   <p><input type="submit" value="Mittel berechnen"></p>
</form>

Das Formular berechnet den Mittelwert einer beliebigen Anzahl von Eingaben. Jedes Mal, wenn der Benutzer einen Wert in ein Feld eingibt, erzeugt die anonyme Funktion ein neues Feld für die nächste Zahl und registriert sich selbst als Event Handler für das neue Feld.

const wert = document.getElementById( 'mit0' );
wert.onfocus = function() {
	this.onfocus = null;
	const newInput = this.cloneNode();
	this.parentNode.appendChild(document.createElement( 'br' ));
	this.parentNode.appendChild( newInput );
	newInput.onfocus = arguments.callee;
};

Die erste Anweisung let wert = document.getElementById('mit0'); liest das Element mit der id mit0 ein – das ist das anfängliche Eingabefeld des Dokuments. Wenn das Feld in den Fokus kommt (beim Klick der Maus in das Feld oder bei einer Navigation mit der Tastatur) meldet this.onfocus = null; die Registrierung für das Ereignis ab, damit unentschlossene Benutzern nicht mit jedem Klick in ein Eingabefeld unzählige Eingabefelder erzeugen.

Die nächste Anweisung clont ein neues Eingabefeld und fügt on the fly ein BR- und direkt danach das neu erzeugte INPUT-Element in das Formular ein. Die Rekursion sitzt in der letzten Zeile der anonymen Funktion: newInput.onfocus = arguments.callee;. Die anonyme Funktion registriert sich selbst als Event Handler, wenn das neue Eingabefeld in den Fokus kommt, denn arguments.callee enthält genau die anonyme Funktion.