Was ist rekursives Programmieren?

Kurz gesagt rekursives Programmieren bedeutet, dass eine Funktion oder Methode sich selbst aufruft. Dies hat den Vorteil das der Code eleganter wirkt, sowie Wartbarer und effizienter ist. Ich werde anhand eines Beispiels erläutern, wie diese Programmierart eingesetzt werden kann.

Wikipedia definiert rekursive wie folgt:

Als Rekursion (lateinisch recurrere ‚zurücklaufen‘) bezeichnet man den abstrakten Vorgang, dass Regeln auf ein Produkt, das sie hervorgebracht haben, von neuem angewandt werden. Hierdurch entstehen potenziell unendliche Schleifen. Regeln bzw. Regelsysteme heißen rekursiv, wenn sie die Eigenschaft haben, Rekursion im Prinzip zuzulassen.

Palindrom Beispiel

Das Beispiel wird ein Palindrom-Tester sein, ein Palindrom ist ein Wort das Vorwärts sowie Rückwärts gleich geschrieben wird z.B. Regallager oder Rentner. Um dies zu prüfen habe ich folgende Funktion entworfen:

function isPalindrome(myString) {
    if (myString.length <= 1) return true;
    if (myString.charAt(0) != myString.charAt(myString.length - 1)) return false;
    return isPalindrome(myString.substr(1, myString.length - 2)); 
}

Wie man sehen kann wird in Zeile 3 die Funktion selbst aufgerufen, daran erkennt man das es sich um eine rekursive Funktion handelt.

Jetzt aber von Anfang an, Zeile 1:

if (myString.length <= 1) return true;

Hier wird geprüft ob der String 1 Zeichen lang ist, da ein Zeichen Vorwärts und Rückwärts gleich ist muss es ein Palindrom sein.

Zeile 2:

if (myString.charAt(0) != myString.charAt(myString.length - 1)) return false;

Jetzt prüft die Funktion ob das erste Zeichen und das letzte Zeichen identisch ist, wenn nein soll die Funktion false zurückgeben.

Zeile 3:

return isPalindrome(myString.substr(1, myString.length -2));

Jetzt geht es los, hier wird die Funktion zu einer rekursiven Funktion, da die Funktion sich selbst aufrufen tut. Als Parameter wird der String übergeben, aber vorher wird der String noch beschnitten. Es wird das erste und das letzte Zeichen entfernt. So wird der String von außen nach innen durchgearbeitet.

Debug Beispiel

function isPalindrome(myString) {
    if (myString.length <= 1) return true;
    console.log("(length > 1) = false");
    if (myString.charAt(0) != myString.charAt(myString.length - 1)) return false;
    console.log("(char 1 == char last) = true");
    return isPalindrome(myString.substr(1, myString.length - 2)); 
}

console.log(isPalindrome("Rentner".toUpperCase()));

Gibt folgendes Aus:

(length > 1) = false
(char 1 == char last) = true
(length > 1) = false
(char 1 == char last) = true
(length > 1) = false
(char 1 == char last) = true
-> true

Es muss vorher toUpperCase angewandt werden, da sonst false ausgegebn wird, da R != r.

console.log(isPalindrome("Palindrome".toUpperCase()));

(length > 1) = false
-> false

verschachteltes Objekt analysieren

In diesem Beispiel erläutere ich, wie man ein Objekt, mit einer Baumstruktur, mit einer rekursiven Funktion analysiert. Zum Beispiel, du hast ein Object in dem ein Array ist, in diesem wiederum mehrere Objekte mit jeweils einem Array ist und diesen Array ist wieder ein Objekt mit einem Array usw.. Praktisches Beispiel: ein Umfragetool mit N Unterkategorien hat Fragen die Pflichtfelder sind und neben diesen Fragen kann es wieder eine Unterkategorie geben mit nicht Pflichtfeldern geben. Jetzt ist die Aufgabe, eine Anzeige zu entwickeln die anzeigt wie viele Pflichtfelder es gibt.

Beispielobjekt

In diesem Beispiel gibt „state“ an, ob es sich um Pflichtfelder handelt.

let myObj = {
  nestedObj: [
    {
      questions: [{},{}],
      state: true,
      nestedObj: [
       {
        questions: [{},{}],
        state: false
       },
       {
        questions: [{}],
        state: true,
        nestedObj: [
         {
           questions: [{},{}],
           state: true
         },
         {
           questions: [{}],
           state: false
         }
        ]
       }
     ]
    }
  ],
  questions: [{},{},{}],
  state: true
}

Jetzt willst du herausfinden, wie viele „questions“, mit dem „state“ true, existieren. Das Problem ist dabei, das es sich um eine Baumstruktur handelt. Deswegen kann es passieren, dass die rekursive Funktion sich mehrfach selbst aufruft. Deswegen muss der Ausgangswert mal X Objekte im Array subtrahiert werden.

const reducer = (accumulator, currentValue) => accumulator + currentValue;
function countQuestions(obj, count = 0) {
  if(obj.state)
    count += obj.questions.length;
  
  if(typeof obj.nestedObj != 'undefined' && obj.nestedObj.length != 0){
    return obj.nestedObj.map(nestedObj => countQuestions(nestedObj, count)).reduce(reducer) - (count * (obj.nestedObj.length-1));   
  }
  else
    return count;
}

Code Analyse

const reducer = (accumulator, currentValue) => accumulator + currentValue;

Das ist eine Helferfunktion für reduce, hierdrauf werde ich nicht weiter eingehen, einfach auf MDN web docs nachlesen was da passiert. Hinsweis: es handelt sich um eine ES6 Arrow Funktion.

if(obj.state)
    count += obj.questions.length;

In dieser If Abfrage, wird geprüft ob „state“ true ist und somit als Pflichtfeld gilt. Falls die Bedinung true, also Wahr, ist, sollen die Artikelanzahl summiert werden.

if(typeof obj.nestedObj != 'undefined' && obj.nestedObj.length != 0){
    return obj.nestedObj.map(nestedObj => countQuestions(nestedObj, count)).reduce(reducer) - (count * (obj.nestedObj.length-1));   
}

Jetzt geht es ans eingemachte, zuerst wird geprüft ob das Objekt überhaupt ein Array hat und ob dieses auch Elemente beinhaltet.

obj.nestedObj.map(nestedObj => countQuestions(nestedObj, count))

Die Map Funktion in Kombination mit der Arrow Funktion, ruft die rekursive Funktion mehrfach auf. Sprich die Map Funktion würde ein Array mit der Anzahl der Pflichtfelder + der bisherigen gezählten Pflichtfelder zurückgeben. Beispiel: aktuell 3 Pflichtfelder und es gibt 2 Sub-Elemente mit jeweils 2 Pflichtfeldern, würde Map [5,5] zurückgeben.

.reduce(reducer)

Addiert alle Zahlenwerte im Array, bleiben wir bei dem Beispiel mit [5,5], würde reduce 10 zurückgeben.

- (count * (obj.nestedObj.length-1)

Da wir Ja nicht 10 Pflichtfelder haben, sondern 3 + 2 + 2 = 7, müssen wir den Basiswert (3) N-1 mal von dem Ergebnis abziehen, in diesem Fall: 2 Objekte – 1 = 1. Spricht unsere Rechnung: (3 + 2) + (3 + 2) – (3 * 1).

in JSBin öffnen