Schnelles Code-Beispiel
$x = 0;
rekursiv();
function rekursiv(){
global $x;
echo $x++ . " ";
if($x < 10){
rekursiv(); // Recursive call
}
}
// 0 1 2 3 4 5 6 7 8 9
- Unterschied iterativ und rekursiv
- Rekursive Funktion
- Übungen
Inhaltsverzeichnis
Unterschied iterativ und rekursiv
Wenn wir ein bestimmtes Problem durch einen Algorithmus lösen wollen, stehen uns zwei Vorgehensweisen zur Verfügung. Beide unterscheiden sich dadurch, auf welche Weise Aktionen wiederholt werden:
- iterativ: Wir führen eine Aktion mithilfe von Schleifen wiederholt durch.
- rekursiv: Die Wiederholung der Aktion erfolgt dadurch, dass sich eine Funktion (mehrmals) selbst aufruft.
Die klassische iterative Variante mit einer Schleife sieht zum Beispiel so aus:
$x = 7;
while($x > 0){
echo $x-- . " ";
}
Eine ganz normale while-Schleife. Die Anweisung innerhalb der Schleife wird solange wiederholt, bis die Schleifenbedingung nicht mehr erfüllt ist. Das Ergebnis sieht so aus:
7 6 5 4 3 2 1
Beispiel Rekursive Funktion
Wie lässt sich dieser Vorgang nun rekursiv durchführen?
Hierzu müssen wir eine Funktion schreiben, die sich selbst aufruft. Diese Funktion wird dann als rekursive Funktion bezeichnet.
Jede rekursive Funktion muss dabei eine Verzweigung als Abbruchbedingung beinhalten, damit die Rekursion irgendwann auch wieder beendet wird. Ansonsten laufen wir in eine Endlosschleife. Wäre nicht so gut :-)
Eine rekursive Funktion, die dem Schleifenbeispiel von oben entspricht, sieht so aus:
$x = 7;
doIt($x);
function doIt(&$x){
echo $x-- . " ";
if($x > 0){
doIt($x); // Rekursion!
}
}
Ok, was ist hier los? Wir übergeben die Variable $x mit dem Wert 7 als Referenz der Funktion doIt(). Innerhalb der Funktion wird der Wert von $x um 1 verringert ($x--) und mit echo am Bildschirm angezeigt.
Als nächstes wird mit der if-Verzweigung geprüft, ob $x noch größer ist als 0. Wenn das so ist, kommt es zur Rekursion: Die Funktion ruft sich selbst auf ($x wird dabei als Argument übergeben).
Schachtelungstiefe
Wenn eine Funktion sich selbst aufruft, kommt es zur Verschachtelung. Bei jedem neuen Funktionsaufruf nimmt die Schachtelungstiefe zu.
Erst wenn im letzten Funktionsdurchlauf $x auf 0 gesetzt wird und damit $x > 0 false ist, wird es keine weitere Rekursion geben!
Übungen
einfach
Was wird am Bildschirm angezeigt?
$counter = 0;
function niceDay(){
global $counter;
$counter++;
echo $counter;
if($counter < 3){
niceDay();
}
}
niceDay();
mittel
Was gibt der folgende Code am Bildschirm aus?
$str = "Flash Gordon";
$n = 0;
fkt1($str, $n);
function fkt1($str, &$n){
switch($str){
case "Flash Gordon":
$n = 1;
case "Mandrake":
$n = 2;
break;
case "Phantom":
$n = 3;
}
fkt2($n);
}
function fkt2(&$n){
$n++;
if($n != 5){
echo $n;
fkt2($n);
}
}
schwer
Wandeln Sie die folgende Iteration mit Schleife in eine Rekursion um:
for($i = 1; $i < 11; $i++){
if(($i / 2) > 3){
echo $i . " <br> ";
}
}
// 7 8 9 10