[Jojo]

Eine praktische Einführung in die Rekursion


Inhalt

1. Was ist eigentlich Rekursion?
2. Wie sehen rekursive Funktionen aus?
3. Wie funktionieren nun rekursive Funktionen?
4. Wo setzt man rekursive Funktionen ein?
5. Wie konstruiere ich nun eine rekursive Funktion?
6. Und wieso der ganze Umstand?
7. Die Nachteile der Rekursion

Vorwort

Hallo. Hast du keinen Schimmer, was Rekursion ist? Oder hast du schonmal etwas darüber gehört und möchtest jetzt mal wissen was das eigentlich genau ist und wie man es anwendet?
Dann bist du hier genau richtig. Denn mit diesem kleinen Tutorial versuche ich, dir die Welt der Rekursion ein wenig näher zu bringen. Erstens ist Rekursion nämlich gar nicht so schwer und zweitens kann sie einem manchmal das Leben sehr erleichtern. Es lohnt sich also auf jeden Fall hier rein zu schnuppern.


Was lernst du hier?

In 7 Kapiteln lernst du hier...

• was Rekursion eigentlich ist
• wozu man sie benötigt
• wie man sie praktisch anwendet
• was sie so besonders macht
• und was ihre Nachteile sind

Das Thema Rekursion ist natürlich kein Begriff, der nur in PHP vor kommt. In allen Programmiersprachen wird Rekursion angewandt. Wir werden aber unsere Beispiele alle in PHP programmieren. Du kannst dich aber nach dem Tutorial gerne mal in Java versuchen. Wenn dir das in Java zu einfach erscheint, kannst du auch gerne mal Prolog oder Scheme ausprobieren.


Wie benutze ich dieses Tutorial?
In diesem Tutorial wird dir wahrscheinlich viel Unbekanntes begegnen. Solltest du einen Beispielcode nicht verstehen, gib nicht gleich auf. Meist habe ich bei etwas komplizierten Funktionen oder Konstrukten vorher eine entsprechende Info mit einem weiterführendem Link eingefügt. Es lohnt sich, diese Links im Zweifelsfall zu verfolgen.
Die folgenden Symbole werden dir im Tutorial öfters begegnen:

• Hinter diesem Symbol verbergen sich wichtige Infos und Merksätze, die du dir unbedingt einprägen solltest

• Hier findest du weiterführende oder zusätzliche Informationen zum aktuellen Kapitel
• Sollte dir ein Konstrukt oder eine Funktion unbekannt erscheinen, oder solltest du Probleme bekommen, halte nach diesem Symbol Ausschau.

Wenn du zu guter letzt immer noch Probleme haben solltest: Schlaf mal drüber! Vielleicht siehst du am nächsten Tag alles klarer.
Natürlich kannst du auch einfach nachfragen, wenn du mit deinem Problem nicht weiterkommst.

[Jojo]

1. Was ist eigentlich Rekursion?

Der Begriff Rekursion kommt von dem lateinischen Wort recurrere was soviel heißt wie zurückkommen, wiederkehren. Aber wie? Eine for-Schleife kehrt doch auch wieder, oder nicht?
Das mag zwar stimmen, aber das besondere bei der Rekursion ist die Tatsache, dass ganze Funktionen, Methoden oder ähnliches wiederkehren. Und zwar in der entsprechenden Funktion oder Methode selbst.
Funktion meine_funktion() ruft also in sich selbst meine_funktion() auf. Klingt komisch? Is aber so.

Rekursion bedeutet also, dass eine Methode sich innerhalb ihrer selbst erneut aufruft

Den "normale" Weg über Schleifenkonstrukte wie while, for, etc. nennt man übrigens Iteration. Stellen wir uns die Rekursion mal in PHP vor.

[Jojo]

2. Wie sehen rekursive Funktionen aus?

Eine sehr einfache rekursive Funktion ist beispielsweise diese hier:

PHP-Code:

function meine_rekursive_funktion() {
    meine_rekursive_funktion();
} 


Sollte dir so ein Konstrukt unbekannt erscheinen, lies dir bitte das hier durch, bevor du fortfährst!

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.

Wir sehen also:

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 anderes Beispiel:
Eine Funktion die alle Zahlen von 0 bis zu einer übergebenen Zahl zusammenzählt.

PHP-Code:

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


Wie du siehst, gibt es zwei Wege die zu einem return der Funktion führen. Einer davon ruft die Funktion nicht mehr auf. So etwas benötigen wir in jeder rekursiven Funktion. Unsere Abbruchbedingung ist, dass die übergebene Zahl 0 ist. Denn dann wird "return 0;" ausgeführt und es findet kein weiterer Aufruf von summe() statt.

[Jojo]

3. Wie funktionieren nun rekursive Funktionen?

Betrachten wir noch einmal unsere Summen-Funktion:

PHP-Code:

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?
Nun.
Zuerst wird überprüft, ob 3 ungleich 0 ist, was definitiv der Fall ist. Also wird eine Zahl zurückgegeben. Und was jetzt kommt ist wichtig!
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 die Funktion die Zahl zurückgegeben werden kann, muss also erst summe(2) berechnet werden.

Also wird wiederum die Funktion summe() aufgerufen. Diesmal 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 den Parser wieder dazu anleitet, summe() mit dem Parameter 1 aufzurufen.

1 ist immernoch ungleich 0 und somit wird zurückgegeben 1 + summe(0).
Und wieder ruft der Parser die Funktion summe() auf. Diesmal mit dem Argument 0.

Und hier ist endlich unsere Abbruchbedingung erfüllt. 0 ist gleich 0 und somit wird lediglich 0 zurückgegeben, ohne dass ein weiterer Aufruf von summe() stattfindet.


Und jetzt kommt der springende Punkt.
All diese zusätzlichen Aufrufe von summe() finden verschachtelt während der Ausführung des vorherigen Aufrufes statt.

Das heißt, summe(2) wird während summe(3) aufgerufen,

summe(1) innerhalb von summe(2) und

summe(0) in summe(1).

Das hat zur Folge, dass der Rückgabewert von summe(0) - also 0 - an summe(1) zurückgegeben wird,
der nun endlich seinen Rückgabewert 1 + summe(0) berechnen kann - 1 + 0 = 1.

Und den kann er dann auch endlich an summe(2) geben, der dadurch 2 + summe(1) berechnen kann - 2 + 1 = 3.

Und endlich, endlich bekommt der Funktionsaufruf der schon am längsten wartet, etwas zurückgeben zu können, nämlich summe(3),
die heiß ersehnte Zahl summe(2), mit der er seinen Rückgabewert 3 + summe(2)bilden kann - 3 + 3 = 6.

Und diese Zahl 6 bekomme wir nun zurück, wenn wir summe(3) aufrufen.

------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------

Puhh.... Das war jetzt ganz schön schwer bis hier her. Erstmal durchatmen.
Es war bis jetzt auch ganz schön theoretisch.
Es geht aber auch anders. Schauen wir uns das ganze einmal etwas grafisch aufbereitet an. Dazu betrachtet wir einzeln die Rekursionsstufen der Funktion summe() mit dem Parameter 3.

Was sind Rekursionsstufen, wirst du jetzt vielleicht fragen.
Eine Rekursionsstufe ist der Grad der Rekursion, in der wir uns befinden.
Sie sagt uns, wie tief wir in der Rekursion stecken. Die Rekursionsstufen fangen bei 1 an und erhöhen sich mit jedem rekursiven Aufruf der Funktion - ausgehend von der Stufe, in der der rekursive Aufruf statt findet.

Die Rekursionsstufe gibt uns den Grad oder die Tiefe der Rekursion an, in dem wir uns gerade befinden.

Beim Aufruf von summe(3) befinden wir uns noch in Stufe 1.
Wenn dann summe(2) rekursiv aufgerufen wird, landen wir in Stufe 2, usw.
Bis wir beim Aufruf von summe(0) in der höchsten Rekursionsstufe 4 landen. Hier geht es nicht tiefer. Nur zurück.

Wenn beim Zurückgehen auf einer kleineren Rekursionsstufe erneut ein Aufruf von summe() stattfindet, wird nicht von der maximalen Rekursionsstufe aus gezählt, sondern von der, in der der Aufruf stattfindet.

Sollte beim Zurückrechnen auf Stufe 2 ein weiterer Aufruf von summe() fällig sein, ist die neue Stufe nicht 5, sondern - ausgehend von Stufe 2 - 3.

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. Daher ist an dieser Stelle 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.

Wir sehen also:

Eine Rekursionsstufe gibt also ihren Rückgabewert immer an die Rekursionsstufe zurück, in der sie aufgerufen wurde.

So, noch da? Gut.
Das war jetzt ein ganzer Haufen Information. Lehn dich jetzt erst einmal zurück und ordne deine Gedanken.
Denn im nächsten Kapitel lernst du, wo du überall Rekursion einsetzen kannst und du lernst das Teile-und-Herrsche-Prinzip kennen.

[Jojo]

4. 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.

Wenn wir so weitermachen, kommen wir auf die ersten 10 Fibonacci-Zahlen:
0.: 0
1.: 1
2.: 2
3.: 3
4.: 5
5.: 8
6.: 13
7.: 21
8.: 34

Unsere Problemstellung:
Wir suchen eine Funktion, die uns das n-te Glied der Fibonacci-Folge liefert.

Überprüfen wir nun mal, ob wir unser Problem rekursiv lösen können!

Als Beispiel nehmen wir das 5. Glied.
Um das 5. Glied zu bekommen benötige ich 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 ihr da seht ist ein sogenannter Rekursionsbaum. Und zwar einer für die 5. Fibonacci-Zahl.
Dort sieht man schön, 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).

An dem Rekursionsbaum sieht man auch schön das, was wir vorhin in Kapitel 3 erwähnt haben. Jeder Ast hat seine eigene höchste Rekursionsstufe. Denn den Rekursionsbaum kann man auch zeilenweise lesen. Von oben nach unten stellt dann jede Zeile eine Rekursionsstufe dar

Und wir sehen am Rekursionsbaum auch schön, dass unsere 2. Bedingung 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). Unsere 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.

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

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

Nun aber endlich zum Programmieren!

[Jojo]

5. 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 ich kann dir ein paar Sachen zeigen, die mir persönlich die Konstruktion erleichtern.
Wenn ich zum Entschluss komme, den rekursiven Weg dem iterativen vorzuziehen, dann gehe ich vorher (notfalls auf Papier) die folgenden Punkte durch.

1. Was ist überhaupt mein Problem, das ich in Teilprobleme vom gleichen Typ zerlegen will?
2. Welche der Informationen, die ich verarbeite ist dynamisch, muss also per Parameter übergeben werden?
3. Anhand wessen kann ich festlegen, ob die Funktion rekursiv aufgerufen werden soll (Abbruchkriterium)?
4. Was soll passieren, falls das Abbruchkriterium zutrifft?
5. Falls nicht: Was soll ausgeführt werden und welche Informationen benötigt mein rekursiver Aufruf?
6. Wie vereine ich die Lösung aller Teilprobleme wieder zur Lösung des Originalproblems?
7. Könnte es Fälle geben, bei denen mein Aufruf zu einer Endlosschleife führen könnte?

Überlegen wir uns das einmal anhand der Fibonacci-Funktion:

1. 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.
2. Die Funktion benötigt nur eine Information, nämlich die Nummer des Gliedes, das sie bilden soll (n).
3. 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.
4. 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.
5. 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.
6. 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) )
7. 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.

So dann machen wir uns mal ans Programmieren:

Erstellen wir erst einmal unseren Funktionsbody:

PHP-Code:

function fib($n) {
} 


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

PHP-Code:

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


Wie du sehen kannst, habe ich 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 verhindere ich erfolgreich die Endlosschleife.

Nun aber zum rekursiven Part.
Der ist recht simpel:

PHP-Code:

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


So! Mehr ist es nicht. "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.


"Schön!", wirst du sagen. "Und was kann ich damit anfangen? Sowas benutze ich doch nie!".
Um dir zu beweisen, dass man Rekursion auch gut in der Praxis anwenden kann, habe ich hier ein anderes Beispiel für dich, was du vielleicht auch in der Praxis anwenden kannst.

[Jojo]

6. Und wieso der ganze Umstand?

Nun, eine berechtigte Frage, sicherlich.
Das Schöne an der Rekursion aber ist, dass man dadurch viele Probleme einfach lösen kann, die bei einem iterativen Ansatz äußerst viel Planung beanspruchen würden, oder aber einen extrem aufwändigen Code zu Tage fördern würden.
Eine rekursive Funktion zu basteln ist vielmals schlichtweg einfacher als eine iterative. Versuche einmal selbst eine iterative Lösung für das Problem der Fibonacci-Folge zu entwerfen. Sicherlich nicht unmöglich, aber doch schwieriger.
Und länger, wenn man sie mit der rekursiven Funktion vergleicht, die ich mittels des ternären Operators auf eine Zeile im Body gekürzt habe:

PHP-Code:

 function fib($n) {
         return ($n < 2) ? $n : fib($n-1) + fib($n-2);
} 


schön nicht?

Dir ist das Konstrukt unbekannt? [post=90"]Hier[/post] kannst du mehr zum ternären Operator erfahren.

[Jojo]

7. Die Nachteile der Rekursion

Schönheit ist nicht alles. Geschwindigkeit zählt oft viel mehr. Und da liegt auch die große Schwäche der meisten Rekursionen gegenüber den Iterationen.
Dadurch, dass beim rekursiven Aufruf einer Funktion jedesmal die gesamte Funktion neu gestartet werden muss, entsteht eine Menge zusätzlicher Ressourcenverbrauch.
Wie schlimm sich das auswirkt, ist von Sprache zu Sprache unterschiedlich. Der Java-Compiler zum Beispiel versucht, Rekursionen intern zu Iterationen umzuformen, um damit die Anwendungen performanter zu machen.

Um zu zeigen, wie sehr die Performance unter einer Rekursion leidet, brauchen wir keinen umständlichen Code. Wir gehen ein Stück zurück und greifen uns die Summenfunktion von vorhin.
Mit diesem Code wollen wir die Performance "messen".
Ich habe die rekursive Funktion übrigens (so wie oben) mit Hilfe des ternären Operators gekürzt. Bei der unteren Funktion lasse ich mit Hilfe einer for-Schleife alle Zahlen von 0 bis zu dieser Zahl zusammenzählen.

Hilfe zu for bekommst du hier.

PHP-Code:

function summe_rek($zahl) {
 return ($zahl != 0) ? $zahl + summe_rek($zahl - 1) : 0;
}

function summe_it($zahl) {
 $summe = 0;
 for ($i = 0; $i <= $zahl; $i++) {
  $summe += $i;
 }
 return $summe;
}

$now = microtime();
summe_rek(3);
echo "Zeit rekursiv: " . (microtime() - $now) . "Mikrosekunden\n";

$now = microtime();
summe_it(3);
echo "Zeit iterativ: " . (microtime() - $now) . "Mikrosekunden\n"; 


Das $i++ nennt man übrigens Inkrementieren und ist die Kurzform von $i = $i +1. Das ganze gibt es auch noch mit Minuszeichen. Dann nennt man das Dekrementieren.

Wir (oder zumindest ich ) bekommen folgende Ausgabe:

Zeit rekursiv: 5.4E-05Mikrosekunden
Zeit iterativ: 2.7E-05Mikrosekunden

hmm.... Die Iteration hat die Hälfte der Zeit gebraucht. "Ok", wirst du sagen. "Das sind ein paar Mikrosekunden. Sogar nur Bruchteile davon!".
Dann erhöhen wir doch mal n auf 10000.
Da sieht die Sache schon anders aus:

Zeit rekursiv: 0.139699Mikrosekunden
Zeit iterativ: 0.006515Mikrosekunden

Obwohl die Zahlen immer noch klein sind, fällt der große Unterschied ins Auge.
Und jetzt stell dir mal den Code ein wenig komplizierter vor. Oder wie wärs, wenn du ihn mehrfach anwenden müsstest?
Der Code würde immer langsamer und langsamer und laaaaaaangsaaaaa.... Naja, lassen wir das

Du siehst:
Rekursionen sind schnell gebaut, werden aber auch schnell unperformant, wenn die Tiefe der Rekursion zunimmt. Allerdings gibt es Probleme, bei denen iterative Lösungen extrem schwer sind und eventuell sogar noch unperformanter als die rekursive Ausführung.


Bei manchen Rekursionen ist es möglich, bereits errechnete Ergebnisse zwischenzuspeichern - das nennt man cachen - und bei erneutem Bedarf gerade auszulesen. Bei der Fibonacci-Folge bietet sich dieses Verfahren an. Diese Änderung im Algorithmus kann erheblich zur Steigerung der Performance beitragen.

Eine gute Struktur des Algorithmus ist wichtig für die Performance. Die Struktur kann man zum Beispiel optimieren, indem man früh erkennt, wie viele Rekursionen überhaupt notwendig sind. So könnte man beispielsweise bei dem Fibonacci-Algorithmus testen, ob n-1 oder n-2 bereits 0 oder 1 sind und dann keinen rekursiven Aufruf starten.
Du kannst ja mal überlegen, ob du selbst ein paar Optimierungen einbauen kannst.

[Jojo]

zu guter Letzt kommen wir nun zum

Fazit

Rekursionen sind sinnvoll! Gerade wenn es um komplizierte Probleme geht. Aber sie werden unperformant, wenn die Tiefe der Rekursion zunimmt. Durch Optimierung kann man viel verbessern, aber manchmal kann man kaum optimieren.
Ich nutze Rekursionen immer dort, wo ich keine allzu vielen Rekursionsstufen zu erwarten habe, zum Beispiel beim rekursiven Erstellen von Ordnern.



Ich hoffe, euch hat unser kleiner Ausflug in die Rekursion Spaß gemacht und ihr habt nebenbei etwas gelernt.
Für Fragen und Anregungen stehe ich gerne im PHP-Forum zur Verfügung.

Jojo