Was ist rekursives Programmieren?

Was ist rekursives Programmieren
jetzt liken

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 Programmier Art 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
jetzt liken