Rekursionen in PHP
Weil Gerrit gerade fragt, wie er sein Problem mit Rekursionen beheben kann, hier ein kurzer Überblick über Rekursionen:
Eine Rekursion wird in akademischer Literatur vor allem mit dem Problem der Türme von Hanoi in Verbindung gebracht. Etliche Informatikschüler wurden damit bereits gequält.
In praktischen PHP-Szenarien existieren oft auch rekursive Probleme, wie zum Beispiel das Einlesen einer noch nicht bekannten Verzeichnisstruktur in ein Array. Ich habe dazu mal zwei Funktionen gebaut, die eine Verzeichnisstruktur ausgeben. Einmal rekursiv und einmal iterativ:(Funktioniert praktisch wie bei SelfPHP)
Rekursiv:
function listFiles($directory = './') {
$res = dir($directory);
while ($file = $res->read()) {
if ($file != '.' AND $file != '..') {
if (is_dir($directory . '/' . $file)) {
listFiles($directory . '/' . $file);
} else {
// echo $directory . '/' . $file . '';
}
}
}
$res->close();
}
Iterativ:
function listFilesIterative($directory = './') {
$buffer = array($directory);
while ($buffer) {
$current = array_shift($buffer);
$res = dir($current);
while(false !== ($file = $res->read())){
if ($file != '.' AND $file != '..') {
if (is_dir($current . '/' . $file)) {
// array_push($buffer, $current . '/' . $file);
$buffer[] = $current . '/' . $file;
} else {
// echo $current . '/' . $file . '';
}
}
}
$res->close();
}
}
Beide liefern das gleiche Ergebnis. Zum Thema Schnelligkeit lässt sich nicht viel sagen. In meinen Testfällen unterschieden sich die beiden Funktionen nur minimal von der Geschwindigkeit – sogar ein Vorteil für die ein oder andere Methode lässt sich nicht erkennen.
Doch was ist der Nachteil an rekursiver Programmierung? Nun, manche Sprachen sehen das im Konzept nicht vor – einige erlauben es, aber nur mit einer Einschränkung der Rekursionstiefe. So gibt es in PHP zum Beispiel den php.ini-Wert “backtrack_limit”. Einmal überschritten, steigt der Parser aus. Fatal, wenn das Script große Verzeichnisse (oder andere rekursive Aufgaben) untersuchen soll. (Es gibt aber auch Sprachen, deren Konzept auf Rekursionen beruht)
Nun weiß ich nicht genau, was Gerrits Loudblog da genau macht, aber der Beschreibung nach hört es sich nach irgendwie nach preg_replace_callback an. Oder zumindest so ähnlich…
Die einfachste Lösung wäre tatsächlich wahrscheinlich ein
ini_set('backtrace_limit', 0);
ini_set('pcre.backtrack_limit', 0);
ini_set('pcre.recursion_limit', 0);
vor den Code zu schalten.
Notiz für mich: http://swtch.com/~rsc/regexp/regexp1.html liefert einen sehr fundierten Überblick. Danke, Søren!
Aber vielleicht kannst du, Gerrit, ja mal den entsprechenden Source-Code-Teil posten, damit man sich nicht durch das komplette Loudblog kämpfen muss ;-)