Suchen
Inside Wiki
Nützliche Links




 
phpforum.de bei Facebook
 
phpforum.de bei Twitter
 

Zurück   PHP Forum: phpforum.de > phpforum.de Wiki > phpforum.de Wiki

PHP Wiki Dieses Wiki sammelt Lösungen, zu Problemen, welche immer wieder im Forum auftauchen.

 
 
Artikel-Optionen Ansicht
  #1  

Standard Rekursion

 
Rekursion
 

Allgemein



Eine Funktion wird als rekursiv bezeichnet, wenn sie sich innerhalb ihres Codekörpers selbst erneut aufruft. Dabei gilt wie bei jedem Funktionsaufruf, dass der Code der neu aufgerufenen Funktion komplett abgearbeitet wird, bevor der Code in der aufrufenden Funktion weiter ausgeführt wird.

PHP Quellcode:
function a() {
  echo "Hello World!\n";
  a(); // Rekursiver Aufruf
}

Beispiel 1

Da ein rekursiver Aufruf wie in Beispiel 1 zu einer Endlosschleife führt, muss jede rekursive Funktion eine Abbruchbedingung enthalten.

PHP Quellcode:
function a($n) {
  $q = $n;
  if ($n > 0) { // Abbruchbedingung
    $q += a($n - 1); // Rekursiver Aufruf
  }
  return $q;
}

echo a(10); // Ausgabe: 55

Beispiel 2

Die Funktion in Beispiel 2 ruft sich so lange selbst neu auf, wie der Wert des Parameters $n größer als 0 ist. Bei jedem rekursiven Aufruf wird $n jedoch um 1 reduziert übergeben, sodass die Bedingung beim $n-ten Schritt nicht mehr erfüllt ist und die Rekursion abbricht. Anschaulicher ausgedrückt wird hier also der Code bis zum rekursiven Aufruf zuerst im ersten Durchlauf der Funktion und zuletzt im $n-ten Durchlauf ausgeführt, der Code danach in umgekehrter Reihenfolge vom $n-ten Durchlauf bis zum ersten.

Zusätzlich wird in der Variablen $q der übergebene Wert von $n zum Rückgabewert des nächsten Rekursionsschritts addiert und dann seinerseits zurückgegeben. Da der zuletzt vor der Abbruchbedingung aufgerufene Funktionsdurchlauf ($n = 0) seinen Wert zuerst zurückgibt, wird so sukzessive die Summe 0+1+2+...+$n errechnet, also die Summe der Zahlen von 1 bis $n.

Diese Aufgabe lässt sich natürlich einfacher iterativ mit einer for-Schleife lösen. Der Einsatz von Rekursion ist dagegen jedoch vor allem im Umgang mit Daten sinnvoll, die hierarchisch in einer Baumstruktur angeordnet sind. Beispiel 3 zeigt eine einfache Möglichkeit (hier theoretisch), jedes Element eines beliebig verästelten Baums zu durchlaufen.

PHP Quellcode:
function a($tree) {
  foreach ($tree->children as $child) { // Abbruchbedingung (keine Kinder)
    // Irgendwelcher Code [...]
    a($child); // Rekursiver Aufruf
  }
}

Beispiel 3



Beispiel: Inhaltsverzeichnis



Ein häufig anzutreffendes Beispiel für eine Baumstruktur ist ein Inhaltsverzeichnis oder Seitenmenü, das eine beliebige Anzahl von Einträgen enthält, die über die Angabe einer Index-Nummer (hier: parent_id) jeweils genau einem Elternelement zugeordnet sind.

PHP Quellcode:
$menu = array(
     // 0   1          2
     // id  parent_id  text
  array( 1,      null, 'Item 1'),
  array( 2,      null, 'Item 2'),
  array( 3,         1, 'Item 1.1'),
  array( 4,         2, 'Item 2.1'),
  array( 5,         2, 'Item 2.2'),
  array( 6,         1, 'Item 1.2'),
  array( 7,         4, 'Item 2.1.1'),
  array( 8,      null, 'Item 3')
);

Beispiel 4

Die in Beispiel 4 dargestellte Datenstruktur wird im Normalfall aus einer Datenbanktabelle ausgelesen. Um den Code auch ohne Datenbankabfrage läuffähig zu machen, wurde hier der Inhalt einer Datenbanktabelle mit Arrays direkt in PHP nachgebaut. Das hat allerdings den Nachteil, dass statt verständlicher Bezeichnungen für die Felder der Unter-Arrays ("id", "parent_id", "text") lediglich die in Beispiel 4 darüber notierten numerischen Indizes zum Zugriff auf die Daten verwendet werden können.

PHP Quellcode:
function displayChildren(array $data, $parent_id, $depth) {
  $s = '';
  foreach ($data as $item) { // Gesamtes Feld durchlaufen
    if ($item[1] == $parent_id) { // Aktives Element ist Kindelement
      $s .= str_repeat('  ', $depth) . $item[2] . "\n"; // An Rückgabe anhängen
      $s .= displayChildren($data, $item[0], $depth + 1); // Rekursiver Aufruf
    }
  }
  return $s;
}

echo displayChildren($menu, null, 0);

Beispiel 5

Beispiel 5 zeigt eine rekursive Funktion, die die Baumstruktur durchläuft und geordnet mit korrekt eingerückten Unterebenen als String zurückgibt. Die Idee dahinter ist, pro Durchlauf alle Elemente zu finden, die den übergebenen Index ($parent_id) als Feld-Index "parent_id" (hier numerischer Index 1) gesetzt haben. Der Text (hier numerischer Index 2) jedes dieser Elemente wird an die Ausgabe angehangen und die Funktion danach mit der Index-Nummer des aktuellen Elements als neuer parent_id rekursiv aufgerufen. Im nächsten Schritt werden so diejenigen Elemente gefunden, die wiederum das gerade aktive Element als Elternelement gesetzt haben. Dies wird so oft wiederholt, bis zu einem Element eines Unterzweigs keine weiteren Kindelemente mehr gefunden werden (Abbruchbedingung). Da die Elemente der obersten Ebene eine parent_id von null gesetzt haben, wird beim Funktionsaufruf mit diesem Index begonnen.

Die optische Einrückung der Ausgabe wird vom Parameter $depth gesteuert. Pro Rekursionsebene wird $depth um 1 erhöht, sodass entsprechend mehr Leerzeichen vor die Ausgabe des Texts eines gefundenen Elements eingefügt werden.


Rekursion vs. Iteration



Die Bereiche von Rekursion und Iteration werden sehr oft durcheinander gebracht. Grundsätzlich sollte man sich bemühen, jedes Problem, was eine Wiederholung benötigt, iterativ, also mit Schleifen zu lösen. Es gibt mehrere Gründe:
  • Jeder Funktionsaufruf belegt Speicher auf der RAM des Servers, somit benötigen rekursive Aufrufe mehr Speicher zur Laufzeit.
  • Rekursion kann sehr schnell unübersichtlich und schwer durchschaubar werden.
  • Durch die Funktionsaufrufe sind rekursive Implementierungen sehr langsam.

In PHP ist die Anwendung der Rekursion, wie auch in anderen Sprachen, sehr selten. Die Hauptanwendungsgebiete sind das sortieren von verketteten Listen, binären Bäumen oder speziell in PHP z.B. Arrays, wo die Benutzung der Iteration und Schleifen nachteilhaft wäre.


Mitwirkende: Marc Ermshaus, Ad aCTa
Erstellt von Marc Ermshaus, 30.04.2009 am 01:38
Zuletzt bearbeitet von Marc Ermshaus, 08.05.2009 am 02:12
0 Kommentare , 5975 Betrachtungen

Dieser Text steht unter der GNU-Lizenz für freie Dokumentation


 

Lesezeichen

Stichworte
grundlagen, recursiv, rekursion

Artikel-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.

Gehe zu
Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
Verzeichnis Rekursion Prayerw PHP 12 05.06.2007 22:47
Rekursion Heribert Datenbanken 1 07.07.2005 00:24
Hilfe bei Rekursion! M3 PHP 14 24.05.2005 09:58
rekursion in smarty ? chaosgod PHP 4 20.05.2005 22:42
Verständnis Rekursion: davido PHP 4 28.09.2004 22:41


Alle Zeitangaben in WEZ +2. Es ist jetzt 19:15 Uhr.


Powered by vBulletin® Version 3.8.8 (Deutsch)
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Powered by NuWiki v1.3 RC1 Copyright ©2006-2007, NuHit, LLC