Sie werden nun noch eine weitere Methode kennenlernen, Funktionen zu verwenden. Es handelt sich dabei um rekursive Funktionen. Dies ist eine Funktion, die sich selbst aufruft. Rekursive Funktionen werden vor allem dort eingesetzt, wo man nicht genau vorherbestimmen kann, wie verschachtelt eine Datenstruktur ist.
Rekursion allgemein
Unter einer Rekursion versteht man die Definition eines Programms, einer Funktion oder eines Verfahrens durch sich selbst. Rekursive Darstellungen sind im Allgemeinen kürzer und leichter verständlich als andere Darstellungen, da sie die charakteristischen Eigenschaften einer Funktion betonen.
Ein Algorithmus heißt rekursiv, wenn er Abschnitte enthält, die sich selbst aufrufen. Er heißt iterativ, wenn bestimmte Abschnitte des Algorithmus innerhalb einer einzigen Ausführung des Algorithmus mehrfach durchlaufen werden. Iteration und Rekursion können oft alternativ in Programmen eingesetzt werden, da man jede Iteration in eine Rekursion umformen kann, und umgekehrt. In der Praxis liegt jedoch oftmals die iterative oder die rekursive Lösung auf der Hand und die jeweils alternative Form ist gar nicht so leicht zu bestimmen.
Hinweis: Programmtechnisch läuft eine Iteration auf eine Schleife, eine Rekursion auf den Aufruf einer Methode durch sich selbst hinaus.
Fallbeispiel
Nehmen Sie einen Papierstreifen und versuchen Sie ihn so zu falten, dass sieben genau gleich große Teile entstehen. Dabei dürfen Sie kein Lineal oder sonst ein Hilfsmittel verwenden. Sie werden feststellen, das die Aufgabe gar nicht so einfach ist!
Wenn Sie statt sieben jedoch acht Teile machen, wird es plötzlich einfach: Einmal in der Mitte falten, dann nochmals falten ...
Genau das ist das Prinzip der Rekursion: Ein Problem wird auf ein »kleineres« Problem zurückgeführt, das wiederum nach demselben Verfahren bearbeitet wird. Rekursion ist eine wichtige algorithmische Technik.
Am obigen Beispiel haben Sie auch gesehen, dass die Lösung einer Aufgabe, wenn sie mit Rekursion möglich ist, sehr einfach gelöst werden kann. Hier nun zwei rekursive Fallbeispiele.
Fakultät einer Zahl n (n!) rekursiv
Bei der Berechnung der Fakultätsfunktion geht man aus von der Definition der Fakultät:
0! = 1
n! = 1 * 2 * 3 * ... * n für n>0
Man beginnt bei den kleinen Zahlen. Der Wert von O! ist 1, der Wert von 1! ist 0!*1, der Wert von 2! ist 1!*2, der Wert von 3! ist 2!*3 usw.
Nimmt man eine Schleifenvariable $i, die von 1 bis n durchgezählt wird, so muss innerhalb der Schleife lediglich der Wert der Fakultät vom vorhergehenden Schleifendurchlauf mit dem Wert der Schleifenvariablen multipliziert werden.
Lösung 1 (iterativ)
<?php
function fak($n) {
$resultat = 1;
for ($i=1; $i<=$n; $i++) {
$resultat = $i*$resultat;
}
return $resultat;
}
echo fak(1) . "<br>";
echo fak(2) . "<br>";
echo fak(3) . "<br>";
echo fak(4) . "<br>";
?>
Ausgabe
1
2
6
24
Bei der rekursiven Berechnung der Fakultätsfunktion geht man ebenfalls von der Definition der Fakultät aus, beginnt jedoch nicht bei den kleinen Zahlen, sondern bei den großen Zahlen und läuft dann zu den kleinen Zahlen zurück (recurrere = lat. zurücklaufen).
n! = 1 * 2 * 3 * ... * n für n>0
0! = 1
Im Gegensatz zur Iteration schaut man jetzt auf die Funktion f(n) und versucht, diese Funktion durch sich selbst, aber mit anderen Aufrufparametern darzustellen.
Die mathematische Analyse ist hier ziemlich leicht, denn man sieht sofort, dass
f(n) = n * f(n-1)
ist. Damit hat man das Rekursionsprinzip bereits gefunden. Die Rekursion darf jedoch nicht ewig andauern, sie muss durch ein Abbruchkriterium angehalten werden. Dies ist die Bedingung 0!=1.
Lösung 2 (rekursiv)
<?php
function fak($n){
if ($n==0) {
return 1;
} else {
return $n*fak($n-1);
}
}
echo fak(1) . "<br>";
echo fak(2) . "<br>";
echo fak(3) . "<br>";
echo fak(4) . "<br>";
?>
Ausgabe
1
2
6
24
Der else-Zweig wird angesprungen, wenn die Abbruchbedingung nicht erreicht wird. Hier ruft die Methode sich selbst wieder auf. Hierbei ist zu beachten, dass die Anweisung, die die Methode aufruft, noch gar nicht abgearbeitet werden kann, solange die aufgerufene Methode kein Ergebnis zurückliefert.
Der if-Zweig wird angesprungen, wenn die Abbruchbedingung erreicht ist.
Um Ihnen die Analyse zu vereinfachen, habe ich die rekursive Lösung etwas angepasst.
<?php
function fak($n){
//Aufruf
echo "Eintritt mit $n<br>";
if ($n==0) {
return 1;
} else {
$ergebnis = $n*fak($n-1);
// Rücksprung
echo "Austritt mit $n: $ergebnis<br>";
return $ergebnis;
}
}
fak(4);
?>
Ausgabe
Eintritt mit 4
Eintritt mit 3
Eintritt mit 2
Eintritt mit 1
Eintritt mit 0
Austritt mit 1: 1
Austritt mit 2: 2
Austritt mit 3: 6
Austritt mit 4: 24
Zu jedem Aufruf gehört auch genau ein Rücksprung! Sie können dies beim Programmablauf mithilfe der eingefügten Ausgabezeilen nachvollziehen.
Man beachte die Anzahl der Aufrufe. Im iterativen Fall wird die Methode ein einziges Mal aufgerufen und im Schleifenkörper n Mal durchlaufen. Bei der rekursiven Berechnung wird die Methode n+1 Mal aufgerufen. Dabei muss jedes Mal Speicherplatz auf dem Stack reserviert werden. Da Parameter als lokale Variablen kopiert werden, wird auch dabei Speicherplatz verbraucht. Bei Rekursionen ist daher unbedingt darauf zu achten, dass die Abbruchbedingung bzw. das Rekursionsende korrekt implementiert wurde.
Türme von Hanoi
Ein Turm aus n verschieden großen Scheiben soll mit möglichst wenig Zügen (Umsetzungen) vom Startplatz S auf den Zielplatz Z transportiert werden. Ein dritter Platz steht als Hilfsplatz H zur Verfügung. Dabei gelten die folgenden Spielregeln:
- Jeder Zug besteht darin, eine Scheibe zu bewegen.
- Niemals darf eine größere Schiebe über einer kleineren Scheibe zu liegen kommen.
Bild 3.9: Türme von Hanoi
Schlüsselprinzip: Rekursion
Wenn wir das Problem in einem etwas einfacher gelagerten Fall lösen können, dann kann man diese Lösung auch für den schwierigeren Fall verwenden.
2 Scheiben:
- übertrage den Turm mit 1 Scheibe vom Start- auf den Hilfsplatz
- bewege die Scheibe 2 vom Start- auf den Zielplatz
- übertrage den Turm mit 1 Scheibe vom Hilfs- auf den Zielplatz
3 Scheiben:
- übertrage den Turm mit 2 Scheiben vom Start- auf den Hilfsplatz
- bewege die Scheibe 3 vom Start- auf den Zielplatz
- übertrage den Turm mit 2 Scheiben vom Hilfs- auf den Zielplatz
...
n Scheiben:
- übertrage den Turm mit n-1 Scheiben vom Start- auf den Hilfsplatz
- bewege die Scheibe n vom Start- auf den Zielplatz
- übertrage den Turm mit n-1 Scheiben vom Hilfs- auf den Zielplatz
Die Baumstruktur beim Aufrufen der Syntax
Bild 3.10: Ablauf der Rekursion
Lösung
<?php
function setzeTurm($n, $start, $ziel, $hilf) {
if ($n>0) {
setzeTurm ($n-1, $start, $hilf, $ziel);
echo("Bewege Scheibe $n vom $start-Platz zum $ziel-Platz.<br>");
setzeTurm ($n-1, $hilf, $ziel, $start);
}
}
setzeTurm (3,'Start','Ziel','Hilfsplatz');
?>
Ausgabe
Bewege Scheibe 1 vom Start-Platz zum Ziel-Platz.
Bewege Scheibe 2 vom Start-Platz zum Hilfsplatz-Platz.
Bewege Scheibe 1 vom Ziel-Platz zum Hilfsplatz-Platz.
Bewege Scheibe 3 vom Start-Platz zum Ziel-Platz.
Bewege Scheibe 1 vom Hilfsplatz-Platz zum Start-Platz.
Bewege Scheibe 2 vom Hilfsplatz-Platz zum Ziel-Platz.
Bewege Scheibe 1 vom Start-Platz zum Ziel-Platz.
Weitere Beispiele für rekursive Probleme sind:
- Wege aus einem Labyrinth
- Sortierverfahren
- Szierpinski-Dreiecke
- Baum des Pythagoras
- Kockkurven
- Julia- und Mandelbrotmengen
- Logistisches Wachstum
- Fibonacchi-Folge
- Springer-Problem
- 8-Damen-Problem
|
SELFPHP
SELFPHP OHG, info@selfphp.de, Impressum, Kontakt