Benutzer-Werkzeuge

Webseiten-Werkzeuge


 [[rekursion:start]] 

Rekursion

Was ist eigentlich Rekursion?

Der Begriff Rekursion kommt von dem lateinischen Wort recurrere was soviel heißt wie zurückkommen, wiederkehren. Aber was bedeutet das genau? Eine for-Schleife kehrt doch auch an ihren Anfang zurück?

Rekursion bedeutet, dass eine Funktion sich innerhalb ihrer selbst erneut aufruft

Den „normale“ Weg über Schleifenkonstrukte wie while, for, u.ä. nennt man übrigens Iteration. Viele Probleme kann man sowohl iterativ als auch rekursiv lösen.

Ein sinnloses Beispiel

Eine sehr einfache rekursive Funktion ist beispielsweise diese hier:

function meine_rekursive_funktion() {
    meine_rekursive_funktion();
}  

Das ist zugegeben eine sehr sinnlose Funktion, denn sie macht ja nichts weiter, außer sich selbst aufzurufen. Doch diese ist nicht nur sinnlos, sondern auch problematisch. Denn wenn wir von einem PHP-Script aus diese Funktion aufrufen, wird das Script nie auf normalen Wege enden. Wir haben sozusagen eine Endlosschleife kreiert, denn ein Aufruf von meine_rekursive_funktion() ruft nur wieder diese Funktion auf, die dann wieder die Funktion aufruft, die dann wieder… und so weiter und so fort.

Wichtiges Prinzip: Eine Rekursive Funktion muss die Möglichkeit haben, ausgeführt zu werden, ohne sich selbst aufzurufen. Ob die Funktion sich selbst aufruft oder nicht, muss anhand einer Abbruchbedingung entschieden werden.

Ein Beispiel aus dem Alltag

Zwei Funktionen, die einen Algorithmus zum Essen einer Pizza implementieren:

function Pizzaessen():
   vom ersten bis zum letzten Bissen:
       schneide diesen Bissen ab und iss ihn auf
   FERTIG
function Pizzaessen():
   wenn Teller leer: FERTIG
   sonst:
      schneide einen Bissen ab und iss ihn auf
      Pizzaessen()

Aufgabe: Welche Funktion ist rekursiv, was ist die Abbruchbedingung?

Ein sinnvolles Beispiel

Eine rekursive Funktion die alle Zahlen von 0 bis zu einer übergebenen Zahl zusammenzählt.

function summe($zahl) {
    if ($zahl != 0) {
        return $zahl + summe($zahl - 1);
    }
    else {
        return 0;
    }
}  

Was passiert nun, wenn wir die Funktion summe() mit dem Argument 3 aufrufen?

  • Zuerst wird überprüft, ob 3 ungleich 0 ist, was definitiv der Fall ist. Also wird eine Zahl zurückgegeben – die Zahl die zurückgegeben wird, muss zuerst noch zusammengesetzt werden: Zurückgegeben wird $zahl + summe($zahl - 1).
  • $zahl ist unsere übergebene 3 und $zahl-1 ist dann 2. Also besteht der Rückgabewert aus 3 + summe(2). Bevor von der Funktion das Ergebnis zurückgegeben werden kann, muss also erst summe(2) berechnet werden. Also wird wiederum die Funktion summe() aufgerufen, dieses Mal allerdings mit dem Parameter 2.
  • Nun wird also wieder zuerst einmal überprüft, ob 2 ungleich 0 ist, was wieder der Fall ist. Also wird zurückgegeben 2 + summe(1), was wieder dazu führt, summe() aufzurufen, dieses Mal mit dem Parameter 1.
  • 1 ist immernoch ungleich 0 und somit wird zurückgegeben 1 + summe(0). Und wieder wird summe() aufgerufen. Diesmal mit dem Argument 0.
  • Jetzt ist die Abbruchbedingung erfüllt. 0 ist gleich 0 und somit wird lediglich 0 zurückgegeben, ohne dass ein weiterer Aufruf von summe() stattfindet.

Die Selbstaufrufe der Funktion wurden praktisch auf einen Stapel gelegt, bis die Abbruchbedingung erreicht wird.

Nun kommt der entscheidende Punkt: Wenn die Abbruchbedingng erreicht ist, ruft sicht die Funktion nicht erneut selbst auf, sondern gibt einfach ein Ergebnis an die darunterliegende Schicht zurück, diese berechnet damit ihr Ergebnis und gibt dieses ebenfalls an die nächste Schicht zurück, solange bis der Stapel abgearbeitet ist und ein Endergebnis ausgegeben wurde.

Schrittweise

Beim Aufruf von summe(3) ensteht also ein Bild mit folgenden Schritten, die von oben nach unten ausgeführt werden. Hier ist deutlich die Verschachtelung der einzelnen Stufen zu sehen

1. Rekursionsstufe: summe(3) gibt 3 +summe(2) zurück und ruft dabei summe(2) auf
  2. Rekursionsstufe:summe(2) gibt 2 + summe(1) zurück und ruft dabei summe(1) auf
    3. Rekursionsstufe: summe(1) gibt 1+ summe(0)zurück und ruft dabei summe(0) auf
      4. Rekursionsstufe: summe(0) gibt 0 zurück. Ein weiterer Aufruf von summe() erfolgt nicht. 
         An dieser Stelle ist die höchste Rekursionsstufe erreicht. 
         Mit Erreichen der höchsten Rekursionsstufe geht das Ganze in der umgekehrten Reihenfolge 
         wieder Schritt für Schritt zurück.
      4. Rekursionsstufe: summe(0) gibt 0 an 3. Rekursionstufe zurück
    3. Rekursionsstufe: summe(1) gibt 1+0=1 an 2. Rekursionstufe zurück
  2. Rekursionsstufe: summe(2) gibt 2+1=3 an die 1. Rekursionstufe zurück
1. Rekursionsstufe: summe(3) gibt 3+3=6 an den User zurück. Die Rekursion ist damit abgeschlossen.

Wo setzt man rekursive Funktionen ein?

Rekursive Funktionen kann man überall da einsetzen, wo das sog. „Teile und Herrsche“-Prinzip greift.

Aber was bedeutet das?

Das bedeutet, dass ein Problem, das wir rekursiv lösen möchten, die folgenden drei Bedingungen erfüllen muss:

  1. das Originalproblem muss sich in kleinere Teilprobleme zerlegen lassen, die von gleichen Typ wie das Originalproblem sind
  2. die Teilprobleme dürfen sich zwar weiter in Teilprobleme zerlegen lassen können, aber nur bis zu einer bestimmten Rekursionstiefe (Abbruchbedingung)
  3. Wenn alle Teilprobleme gelöst wurden, müssen sich alle wieder zur Lösung des Originalproblems zusammensetzen lassen

Was heißt das in der Praxis?

Wenden wir uns einem anderen Beispiel zu, mit dem oft Informatikstudenten im 1. Semester an die Rekursion herangeführt werden: die Fibonacci-Reihe

Die Fibonacci-Reihe ist die Folge der Zahlen, die sich aus den zwei vorherigen Zahlen zusammensetzen. Die 5. Fibonacci-Zahl z.B. wird aus der 4. und der 3. zusammengesetzt.

Es gilt:

fib(n) = fib(n-1) + fib(n-2)

Hier findest du genaueres über die Fibonacci-Reihe und hier über Fibonacci selbst.

Zwei Fibonacci-Zahlen sind dazu schon vorher definiert:

fib(0) = 0

und

fib(1) = 1

Sonst könnte man nämlich gar nicht anfangen.

Wenn wir die 2. Fibonacci-Zahl errechnen wollen, rechnen wir also 0 + 1 = 1. Die 3. wäre dann 1 + 1 = 2, die dritte ist dann 2 + 1 = 3.

Aufgabe: Berechne von Hand die ersten 10 Fibonacci Zahlen. Welches Problem hast du, wenn du die 102. Fibonacci Zahl ausrechnen sollst?

Programmierauftrag

Wir suchen eine (rekursive) Funktion, die uns das n-te Glied der Fibonacci-Folge liefert.

Zunächst überprüfen wir, ob wir unser Problem rekursiv lösen können. Als Beispiel nehmen wir das 5. Glied. Um das 5. Folgenglied zu bekommen benötigt man das 4. und das 3. Glied.

Das deutet schon darauf hin, dass die erste unserer Bedingungen erfüllt ist. Denn fib(5) kann ich in zwei Teilprobleme unterteilen. Und diese Teilprobleme sind vom selben Typ wie unser Originalproblem: fib(4) + fib(3) Jedes dieser Teilprobleme kann ich wiederum in jeweils zwei Teilprobleme unterteilen. Und diese wieder und wieder bis das ganze dann so aussieht:

Was man hier seht ist ein sogenannter Rekursionsbaum für die 5. Fibonacci-Zahl. Man kann erkennen, wie sich nach und nach die (Teil-)Probleme (Quadrate) aufteilen lassen, bis nur noch Probleme mit festgelegten Lösungen - fib(0) und fib(1) - übrig bleiben (Kreise).

Am Rekursionsbaum kann man auch erkennen, dass jeder Ast seine eigene höchste Rekursionsstufe hat Die Rekursionsstufen sind jeweils eine Zeile im Rekursionsbaum.

Und wir sehen am Rekursionsbaum auch schön, dass auch eine Abbruchbedingung erfüllt ist: Irgendwann müssen wir die Probleme nicht weiter unterteilen, da sie bereits eine nicht rekursive Lösung besitzen (das stellen die Kreise da). Die Abbruchbedingung ist also, dass die zu berechnende Fibonacci-Zahl die 0. oder die 1. ist. Denn für diese beiden Zahlen haben wir eine eindeutig definierte Lösung, nämlich 0 bzw. 1.

Nun muss nur noch die dritte Bedingung erfüllt sein. Kann ich durch Lösen aller Teilprobleme das Originalproblem lösen?

Am Rekursionsbaum ist das einfach zu sehen.

  • Mit fib(0) und fib(1) kann ich fib(2) lösen.
  • Mit fib(2) und fib(1) kann ich fib(3) lösen.
  • Mit fib(3) und fib(2) kann ich fib(4) lösen.
  • Mit fib(3) und fib(4) kann ich fib(5), das Originalproblem lösen

Alle drei Bedingungen sind erfüllt. Das Problem folgt dem „Teile und Herrsche“-Prinzip und ist somit durch Rekursion lösbar.

Wie konstruiere ich nun eine rekursive Funktion?

Natürlich gibt es keinen universellen Plan, der für jede rekursive Funktion einen exakten Bauplan bereitstellt, aber grundsätzlich kann man sich die folgenden Fragen stellen:

  • Was ist überhaupt mein Problem, das ich in Teilprobleme vom gleichen Typ zerlegen will?
  • Welche der Informationen, die ich verarbeite ist dynamisch, muss also per Parameter übergeben werden?
  • Wie kann ich festlegen, ob die Funktion rekursiv aufgerufen werden soll oder nichgt (Abbruchkriterium)?
  • Was soll passieren, wenn das Abbruchkriterium zutrifft?
  • Was soll passieren, wenn das Abbruchkriterium nicht zutrifft: Welche Informationen benötigt mein rekursiver Aufruf?
  • Wie vereine ich die Lösung aller Teilprobleme wieder zur Lösung des Originalproblems?
  • Könnte es Fälle geben, bei denen mein Aufruf zu einer Endlosschleife führen könnte?

Aufgabe: Beantworte die obigen Fragen für das Fibonacci Problem schriftlich. Lösung ganz unten auf der Seite. Lade anschließdend die Beispieldatei rekursion.php.zip herunter und erstelle die Funktion, indem du der Anleitung unten folgst.

Die Funktion

Erstellen wir erst einmal unseren Funktionsbody:

function fib($n) {
} 

Noch ziemlich leer. Wir beginnen damit, den Weg zu programmieren, der eingeschlagen wird, wenn das Abbruchkriterium zutrifft:

function fib($n) {
    if ($n < 2) {
        return $n;
    }
} 

Wie du sehen kannst, wurde das Verhindern des Spezialfalles n < 0 und das Abbruchkriterium n = 1 oder n = 2 zusammengelegt. Dabei habe ich mir die Tatsache zu nutze gemacht, dass das 0. und das 1. Glied 0 bzw. 1 als Lösung haben. ist n = 1 wird n zurückgegeben. Genauso bei n = 0. Im Fall n < 0 wird auch einfach die übergebene Zahl zurückgegeben. Damit verhindert man die Endlosschleife.

Nun aber zum rekursiven Part.

function fib($n) {
 if ($n < 2) {
  return $n;
 }
 else {
  return fib($n-1) + fib($n-2);
 }
} 

Die Anweisung return fib($n-1) + fib($n-2); lässt die Funktion eine Rekursionsstufe tiefer gehen und bildet korrekt das n-te Glied der Fibonacci-Reihe.

Bestimmung des GGT

Aufgabe: Zur Berechnung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen kommt häufi der klassische euklidische Algorithmus zum Einsatz. Unten ist die iterative Variante zu sehen:

	$a = $_POST['eingabe1'];
	$b = $_POST['eingabe2'];
 
	if ($a == 0) {
		echo "Der ggT von $a und $b ist: $b";
	} else {
		while ($b != 0) {
			if ($a > $b) {
				$a = $a-$b;
			} else {
				$b = $b-$a;
			}
		}
	echo "Der ggT von " . $_POST['eingabe1'] . " und " . $_POST['eingabe2'] . " ist: $a";
	}
 
  • Erstelle aus den gegebenen Codefragmenten eine Funktion euklid_iterativ, welche den GGT berechnet. Verwende rekursion2.php.zip als Vorlage.
  • Finde eine rekursive Lösung des Problems und erstelle eine Funktion euklid_rekursiv, die ebenfalls den GGT berechnet (Google ist dein Freund!).
Lösung...
  • Da gilt fib(n) = fib(n-1) + fib(n-2), kann ich das Originalproblem in zwei Teilprobleme unterteilen. Eines davon ist die Lösung des vorherigen Glieds n-1 und das andere ist die Lösung des vorvorherigen Gliedes n-2. Also ist fib() mein rekursives Problem.
  • Die Funktion benötigt nur eine Information, nämlich die Nummer des Gliedes, das sie bilden soll (n).
  • Die Fibonacci-Zahlen 0 und 1 sind fest definiert. Diese Probleme müssen nicht weiter zerteilt werden. Das Abbruchkriterium ist also, ob das angeforderte Glied n 0 oder 1 ist.
  • Trifft das Abbruchkriterium zu, wird entweder das 0. oder das 1. Glied verlangt. Dann kann ich einfach 0 beim 0. und 1 beim 1. Glied zurückgeben.
  • Falls das Abbruchkriterium nicht zutrifft, soll die Zahl zurückgegeben werden, die sich aus der Summe des n-1-ten Glieds und des n-2-ten Glieds ergibt. Also muss ich das übergeben Paramter n um 1 und um 2 verringern und fib(n-1) + fib(n-2) zurückgeben.
  • Diese Frage ist leicht beantwortet. Die Lösung der Teilprobleme einer Rekursionsstufe werden mittels Addition zur Lösung eines oder des Problems der übergeordneten Rekursionstufe vereint ( fib(5) = fib(4) + fib(3) fib(4) und fib(3) sind eine Rekursionsstufe tiefer als fib(5). Zusammen ergeben sie fib(5) )
  • Ein wenig Überlegen führt uns zu einem Problem: Was passiert, wenn das Parmeter < 0 ist? Dafür sind die Fibonacci-Zahlen nämlich gar nicht definiert. Außerdem würde ein Startparameter von -5 nie 1 oder 0 erreichen, da man ja vom übergebenen Parameter immer 1 oder 2 abzieht. Dadurch würde die Zahl immer negativer werden und so würde eine Endlosschleife entstehen. Dagegen müssen wir uns schützen.
 [[rekursion:start]] rekursion/start.txt · Zuletzt geändert: 2013/05/15 20:10 von sbel