Rekursiv programmieren mit PHP von Huni

Was ist rekursives Programmieren ?

Um dies zu verdeutlichen, fang ich mal mit einem einfachen Problem an:

Es sollen alle Dateien eines Verzeichnises ausgelesen werden inklusive aller Unterverzeichnisse und allen Dateien in diesen Unterverzeichnissen usw..

Das "Problem" liegt auf der Hand, denn dies lässt sich durch einen streng chronologischen Programmablauf nicht realisieren, denn es ist natürlich nicht bekannt, wieviele und welche Unter und Unter-Unterverzeichnisse das auszulesende Verzeichnis besitzt.

Die folgende Funtion "get_dir()" z.B. gibt lediglich alle Dateien und Verzeichnisse im Verzeichnis $dir aus, jedoch werden die Unterverzeichnisse nicht ausgelesen.

function get_dir ($dir) {
 $fp=opendir($dir);
 while($datei=readdir($fp)) {
  if (is_dir("$dir/$datei") && $datei!="." && $datei!="..") {echo "$datei (dir)<br>";}
  else {echo $datei."<br>";}
 }
closedir($fp);
}

Die Aufruf der Funktion get_dir("./") ergibt dann z.B.:

bla.txt
index.html
bilder (dir)
nix.exe

Wie bekommt man es nun hin, dass das Unterverzeichnis "bilder" und alle Unterverzeichnisse von "bilder" auch noch ausgelesen werden ?
Indem man natürlich die Funktion get_dir() wiederum auf das Verzeichnis "bilder" anwendet und anschliessend auf alle Unterverzeichnisse von "bilder".
Da man dies aber natürlich nicht "per Hand" machen möchte und kann, gibt es nur eine Lösung: Die Fubnktion get_dir() muss sich bei Bedarf, d.h. wenn sie auf ein weiteres Verzeichnis stösst, selber wieder aufrufen und dieses Unterverzeichnis auch auslesen. Trifft sie dann wieder auf Unterverzeichnisse, soll sie sich wiederum selbst aufrufen und auch diese Verzeichnisse auslesen usw..

In unserem Beispiel von oben sähe das dann so aus:

function get_dir ($dir) {
  $fp=opendir($dir);
  while($datei=readdir($fp)) {
   if (is_dir("$dir/$datei") && $datei!="." && $datei!="..") {echo "$datei (dir)<br>";                                                                                         get_dir("$dir/$datei"); }
   else {echo $datei."<br>";}
  }
 closedir($fp);
}

Liegen in unserem Beispiel im Verzeichnis "bilder" nun z.B. die Dateien pic1.gif und pic2.gif und auch noch das Verzeichnis "weitere_bilder" mit den Dateien pic3.gif und pic4.gif, ergibt der Funktionsaufruf get_dir("./") in unserem Beispiel nun:

bla.txt
index.html
bilder (dir)
pic1.gif
pic2.gif
weitere_bilder (dir)
pic3.gif
pic4.gif
nix.exe

Es werden jetzt also wirklich alle Verzeichnisse und Unterverzeichnisse ausgelesen, egal wieviele Unterverzeichnisse, Unter-Unter-Verzeichnisse etc. es gibt.

Diesen "Trick", eine Funktion sich selbst aufrufen zu lassen, nennt man "rekursives Programmieren" oder auch "rekursive Funktionen". Rekursive Funktionen werden in Programmen der verschiedensten Programmiersprachen oft dazu verwendet, um mathematische Funktionen auszuführen und mathematische Probleme zu lösen ("Urbeispiel": Fakultät einer Zahl).
Gerade mit PHP lassen sich aber auch ganz andere (interessantere) Dinge durch rekursive Funktionen realisieren.

Z.B. ist es möglich, eine Suchmaschiene bzw. einen "Crawler" zu programmieren.
Dieser soll z.B. eine Seite auslesen und allen (internen) Links auf dieser Seite folgen und auch diese Seiten wiederum auslesen und vorhandenen Links auf diesen Seiten folgen. Das Prinzip bei der Programmierung und Realisierung eines solchen "Crawlers" ist dasselbe wie bei dem obigen Beispiel.

Die stark vereinfachte Struktur der rekursiven Funtion hierfür würde ungefähr so aussehen:

function crawl($link) {
 - Lese Seite aus
 - Suche (interne) Links
 - Wenn Link gefunden --> crawl (gefundener Link);
}

Die gefundenen Seiten könnten nun nach Stichwörtern indiziert werden oder die meta-tags könnten ausgelesen werden oder ähnliches, so dass im Prinzip eine komplette, klassische Suchmaschiene realisierbar ist.

Ebenfalls können durch rekursive Programmierung komplette "Baumstrukturen" in z.B. Datenbanktabellen festgehalten werden. Eine Tabelle, in der z.B. eine Familienstammbaum erfasst wird, könnte so aussehen (MySql-Tabelle):

Tabelle "Stammbaum"

Möchte man nun z.B. diese Baumstruktur geordnet uns strukturiert ausgeben lassen, geht dies wiederum mit einer rekursiven Funktion:

function get_tree($who,$ebene) {
 $res=mysql_query ("select * from stammbaum where nachfahre_von=$who;");
  while ($verwandter=mysql_fetch_array($res)) {
    echo $ebene.$verwandter[name]."<br>";
    get_tree($verwandter[id],$ebene."&nbsp;&nbsp;&nbsp;&nbsp;");
  }
}

Dies ausgabe der Funktion get_tree(0,"") ergibt nun den (hässlichen) Stammbaum:

Opa August
    Onkel Karl
        Cousin Maik
    Tante Ute
        Cousine Inge
    Mutter
        Ich
        Mein Bruder
            Sohn meines Bruders

Diese Struktur dürfte Vielen aus diversen Foren bekannt vorkommen.
In der obigen Tabelle kann man nun beliebig "Äste" hinzufügen, z.B. den Datensatz id=9, name='Sohn von Cousin Maik' und nachfahre_von=4.
Die Funktion get_tree wird immer den kompletten Satmmbaum, egal wieviele "Ebenen" und "Äste" es gibt, ausgeben.

Was man beachten sollte.

Der grösste Vorteil rekursiver Funtionen, nämlich das zu erfassende Strukturen bis zum bitteren Ende ausgelesen bzw. erfasst werden, kann auch gleichzeitig eine "Falle" darstellen. Wenn man sich z.B. vorstellt, man wendet die hier zuerst besprochene Funktion get_dir() zum Auslesen von Verzeichnissen auf das Root-Verzeichnis "/"eines vollgepackten Rechners an, so kann man sich vorstellen, das dies zum Scheitern verurteilt ist.
Deswegen ist es ratsam, bei solchen Vorhaben eine Abruchbedingung in die Funktion eintufügen.
Dies kann z.B. ein "Timeout" sein, d.h. eine Funktion soll sich nur innerhalb eines bestimmten Zeitrahmens immer wieder selbst aufraufen, oder aber man beschränkt die rekursive Funktion auf eine bestimmte "Ebenentiefe".

Ein Programm mit der Funktion get_dir() und 10 Sekunden-Timeout-Bedingung könnte z.B. so aussehen:

function get_dir ($dir,$startzeit) {
 $fp=opendir($dir);
 while($datei=readdir($fp)) {
   if (is_dir("$dir/$datei") && $datei!="." && $datei!="..")
   {
     echo "$datei (dir)<br>";
     if (time()-$starttime > 10) get_dir("$dir/$datei",$startzeit);
   }
   else {echo $datei."";}
 }
  closedir($fp);
}

// Hauptprogramm
$start=time();
get_dir("./",$start);

Eine Ebenenbeschränkung, d.h. es sollen nur das Verzeichnis "./" und alle Unterverzeichnisse ausgelesen werden, jedoch Unter-Unterverzeichnisse und alles was darunter liegt, nicht mehr, könnte so aussehen:

function get_dir ($dir,$ebene) {
  $fp=opendir($dir);
  while($datei=readdir($fp)) {
    if (is_dir("$dir/$datei") && $datei!="." && $datei!="..")
    {
     echo "$datei (dir)<br>";
     if ($ebene<3) get_dir("$dir/$datei",$ebene+1);
    }
   else {echo $datei."<br>";}
  }
 closedir($fp);
}

//Hauptprogramm
get_dir ("./",1);

Ein weiterer "Nachteil" des rekursiven Programmierens ist natürlich auch, dass komplexere Funktionen als die hier angedeuteten schnell "unberechenbar" werden und es nicht mehr so einfach nachzuvollziehen ist, an welcher Stelle die Funktion was macht, vor allen Dingen in den Situationen, wo man die zu erfassende Struktur nicht schon im Vorraus kennt.

Ebenfalls ist teilweise sehr schwer herauszufinden, warum rekursive Funktionen in bestimmten Situationen sich in einer Art "Endlosschleife" immer wieder selbst aufrufen.
Ein Beispiel dazu ist der oben angesprochene "Crawler". Lässt man diesen ohne Kontrolle einfach auf eine Webseite los, so werden bestimmte Seiten, auf die von mehreren anderen Seiten gelinkt wird, natürlich auch mehrfach durchsucht und die gefundenen Links auf dieser Seite auch immer wieder ausgelesen und durchsucht usw., so dass es quasi kein eine Ende in dieser Prozedur gibt.
Eine Lösung hierzu ist z.B., dass bereits durchsuchte Seiten in einem Array festgehalten werden und vor jedem Selbstaufruf der Funktion überprüft wird, ob die entsprechende Webseite nicht schon durchsucht worden ist.

Auf jeden Fall kann rekursives Programmieren sehr nützlich sein und auch viel Spass machen und ich hoffe, dass der eine oder andere etwas mit diesem Artikel etwas anfangen kann.

Feddich.