Was ist eine rekursive Funktion?

Beispiel rekursiv oder iterativ

Nun einmal ein Beispiel für eine rekursive Lösung des Problems bzw. alternativ für eine iterative Lösung mittels einer Schleife.

Als erstes habe ich hier ein einfaches Beispiel, was auch ziemlich einfach als for-Schleife umzusetzen ist. Hier wird lediglich von einem Wert $i zu 10 hochgezählt.

<?php

function rekursiveCounter($i,$content = ""){

    $content .= "Ich zähle ". $i ." Durchlauf \r\n";

    if($i < 10){
        $i++;
        $content = rekursiveCounter($i,$content);
    }

    return $content;    
}

$text = rekursiveCounter(0);

echo $text;

Dabei wird die rekursiveCounter-Funktion 11 Mal aufgerufen; von 0 bis 10. Alternativ würde dieselbe Funktion mit einer for-Schleife folgendermaßen aussehen:

function iterativerCounter($b){
    $content = "";

    for ($i=$b; $i <= 10; $i++) { 
        $content .= "Ich zähle ". $i ." Durchlauf \r\n";
    }

    return $content;
}

2. Beispiel - Die Fakultät rekursiv berechnen

In diesem Beispiel wollen wir die Fakultät mittels einer rekursiven Funktion berechnen. Du wirst in diesem Beispiel auch wieder eine Abbruchbedingung finden, da sonst wieder eine Endlosschleife entstehen würde.

In unserem Beispiel wollen wir die Fakultät von 8 berechnen.

8! = 8*7*6*5*4*3*2*1 = 40320 # Fakultät von 8

Die Funktion für die Berechnung der Fakultät sieht wie folgt aus:

function fakultaet($n){
    if(!is_int($n)):
        return false;
    endif;

    if($n < 2):
        return 1;
    endif;

    return $n * fakultaet($n - 1);

}

Als erstes prüfen wir in der Funktion, ob $n auch ein Integer ist. Ansonsten geben wir false zurück, da von anderen Datentypen keine Fakultät berechnet werden kann. Danach prüfen wir, ob $n kleiner 2 ist und geben dann entsprechend eine 1 zurück; denn die Berechnung der Fakultät geht nicht in den negativen Bereich, also ist dort Ende. Das ist unsere Abbruchbedingung.

Danach folgt der rekursive Aufruf der Funktion, um die Fakultät zu erhalten.

Der Aufruf hat den folgenden Ablauf, so erhalten wir am Ende 8*7*6*5*4*3*2*1 also 8! bzw. das Ergebnis 40320.

fakultaet(8)
return 8 * fakultaet(8 - 1);
return 7 * fakultaet(7 - 1);
return 6 * fakultaet(6 - 1);
return 5 * fakultaet(5 - 1);
return 4 * fakultaet(4 - 1);
return 3 * fakultaet(3 - 1);
return 2 * fakultaet(2 - 1);
return 1;

Wo ist es sinnvoll, Rekursion einzusetzen?

Rekursionen sind vor allem dann nützlich, wenn es unbestimmt viele Durchläufe gibt - oftmals kann es allerdings auch über eine entsprechende while-Schleife gelöst werden.

Es ist einfach auch eine Geschmackssache, ob ich etwas über eine while-Schleife lösen möchte oder über eine rekursive Funktion.

Folgende Beispiele würde ich zum Beispiel rekursiv lösen:

• Generierung einer Navigation für HTML mit <ul> und <li> Elementen, verschachtelt je nach Tiefe.
• Rekursives Löschen eines Verzeichnisses in PHP - Die Funktion rmdir kann ein Verzeichnis nur löschen, wenn es leer ist. Wenn diese wieder Kindverzeichnisse enthält, ist es notwendig, die Inhalte daraus auch erst einmal zu löschen. Dafür eignet sich Rekursion.
• Eine Webseite mit Blogartikeln mit Kategorien in einer unendlichen Verschachtelung

Fazit

Als Programmierer sollte man beides kennen - rekursive Funktionen und Schleifen.

Denn nur dann kannst du erkennen, wann eine Rekursion wahrscheinlich einfacher ist als eine Schleife anzuwenden oder eben anders herum.

Viel Spaß beim Ausprobieren!