Rekursive Funktion mit unerklärbaren Abbruch

[s.heinrich]

Hallo @all,

meine Frage betrifft die folgende Rekursive Funktion, die als Beispiel herhalten soll, um alles etwas übersichtlicher darzustellen. Das eigentliche Problemscript zeigt die gleiche Auffälligkeit. Bei mir endet die Ausgabe des Wertes ungefähr bei 1170 - nicht bei 2000 - und ich habe keine Erklärung dafür (Tests auf Apache + Win und Apache/Unix).

• Die Suche im Netz war bislang erfolglos.
• Ein Test auf einem anderen Server brachte auch keine Besserung.
• Ressource: 32MB sollten dafür reichen ;-)
• Timeout 5 Minuten (das script braucht nur bis zur letztmöglichen Ausgabe von 1170 ca. 1 Sekunde)
• Ich habe etwas mit output_buffering gespielt, was aber nicht die Lösung war.

<?php
function Test(){
    static $zaehler = 0;
    $zaehler++;
    echo $zaehler.' ';
    if ($zaehler < 2000)Test ();
    $zaehler--;
}
Test();
?>

Wie gesagt: es ist nur ein Beispielscript das mein Problem übersichtlich darstellt .
Wo muss ich Einträge ändern, um zu sehen, was die Funktion leisten soll - php.ini,httpd.conf?
..oder könnte ich vielleicht im Script selbst das Ergbenis verbessern?
Ich habe nicht viel Hoffnung, aber vielleicht gibts ja jemanden hier im Forum, der die Lösung kennt.

Viele Grüße und danke an die, die mir eine Weg aufzeigen können,
Sven

[3DMax]

Re: Rekursive Funktion mit unerklärbaren Abbruch

Original geschrieben von s.heinrich
Wie gesagt: es ist nur ein Beispielscript das mein Problem übersichtlich darstellt .

inwiefern problem?
das script gibt mir die zahlen von 1 bis 2000 aus.

[pekka]

Zeig mal das eigentliche Problemskript.

[onemorenerd]

Es ist etwas ungewöhnlich, Rekursion mit einem static Wert umzusetzen. Normalerweise sieht es doch so aus:

function Test($i) {
    $i++;
    echo $i.' ';
    if ($i < 2000) 
        Test($i);
}
Test(0); 

[ArSeN]

Bei mir funktionierts auch (auch mit dem static) tadellos.

[s.heinrich]

Hallo,

und danke, für Eure Postings.
OK, hier das eigentliche "Problemkind".
(Bitte keine verschachtelten foreach-/for-Schleifen anbieten.)

<?php
error_reporting(E_ALL);

function countChar($str,$search){
    if(trim($str)==false || !strstr($str,$search))return 0;
    $zeichen = array();
    for ($i=0; $i<strlen($str); $i++)
        if(isset($zeichen[$str{$i}]))$zeichen[$str{$i}]++;
        else $zeichen[$str{$i}]=1;
    return $zeichen[$search];
}
function printItem($str,$int){
    echo "<code>($int) $str</code><br>\n";
    return true;
}
function recSet( $ar_pool , $int_zaehler ){
    // 1. Prüfung der Werte (Testlauf)
    // 2. Ersetzen der Sternchen und Ausgabe
    // 3. In jedem Durchlauf wird ein Satz an Zeichen für das Ersetzen 
    //    der Sternchen im nkommenden Durchlauf erzeugt
    //    (Anzahl entspr. der Sternchen).
    global $str_word, $ar_abc, $int_ct_stern, $int_ct_abc, $int_last_x, $int_max_item;
    $int_zaehler++;
    $str_word2=$str_word;//Kopie vom Orig.
    $ar_curr_abc=array();//Werte für 1 Einsatz
    //So oft wie Sternchen vorhanden das Array 
    //mit den zugewiesenen Zeichen durchlaufen
    //Werte Prüfen und Zeichen in curr_abc für das folgende Ersetzen def.
    for($x=0; $x<$int_ct_stern; $x++){
        if(!isset($ar_pool[$x]))die(" ERROR #".__LINE__." [$x] ");
        if($ar_pool[0]>=$int_ct_abc)return;//die(" Pool Ende erreicht ");
        if($ar_pool[$x] == $int_ct_abc)die(" ERROR #".__LINE__." ");
        if(!isset($ar_abc[$ar_pool[$x]]))die(" ERROR #".__LINE__." ");
        $ar_curr_abc[$x]=$ar_abc[$ar_pool[$x]];//zeichen def.
    }
    //Curr Zeichensatz verarbeiten
    foreach($ar_curr_abc as $k => $v){
        $t=strpos($str_word2,'*');
        $str_word2{$t}=$v;
        if(strpos($str_word2,'*')===false)
            if(printItem($str_word2,$int_zaehler)==false)
                die(" ERROR #".__LINE__." ");

    }
    //Neuen durchlauf vorbereiten
    //Rückwärts aktualisieren
    //Letzter zählt immer weiter, andere nur wenn Vorgänger Reset
    $ar_reset=array();//Hilfs-Array, ob 0 im Vorg. wirklich aus einem Reset erfolgte
    for($x=$int_last_x; $x >= 0; $x--){
        if( $ar_pool[$x]+1 == $int_ct_abc && $x!=0 
            && ($x==$int_last_x || isset($ar_reset[$x+1]))){
            $ar_pool[$x]=0;//Reset
            $ar_reset[$x]=true;
        
        //nur beim letzten immer +1, sonst nur wenn Vorgänger Reset
        }elseif( $x==$int_last_x || $x!=$int_last_x 
            && ($ar_pool[$x+1])==0 && isset($ar_reset[$x+1])){
            $ar_pool[$x]++;
        }
    }
    //Ende, wenn Grenzwert für Ausgabe erreicht
    if( $int_zaehler >= $int_max_item){
        return;
    }else{
        recSet( $ar_pool , $int_zaehler );
    }
}
//*** DEFINIERE ***
$int_max_item=2000;
$str_word='a*b*c*d';// (*) Zeichen werden ersetzt (egal, wie viele)
$int_ct_stern = countChar($str_word,'*');//Anzahl Zeichen
$ar_abc=array('ä','ö','ü','ß','+','-','a','b','c','d','e'
    ,'f','g','h','i','j','k','l','m','n','o'
    ,'p','q','r','s','t','u','v','w','x','y','z');//Pool an Zeichen
//$ar_pool defin., $ar_pool[$x]=Wert, Wert wird rekur. hochgezählt
//oder ggf. zurückgesetzt
for($x=0; $x<$int_ct_stern; $x++)$ar_pool[$x]=0;
$int_ct_abc   = count($ar_abc);//Anzahl Zeichen
$int_last_x   = $int_ct_stern-1;// letzter Schlüssel

//*** PRINT INFO ***
echo "<p><b>$int_ct_stern</b> Sternchen gefunden.<br>
    <b>$int_ct_abc</b> Zeichen stehen zur Verfügung.<br>
    Das enstpricht <b>".number_format(bcpow($int_ct_abc,$int_ct_stern,0),0,'','.')
    ."</b> Möglichkeiten<br>
    <b>$int_max_item</b> Einträge sollen ausgegeben werden.</p>\n";

//*** START ***
recSet($ar_pool,0);
echo '<div style="height:300px"></div>';//Space
?>

Ich bin gespannt auf jeden erdenklichen Hinweis!
Danke!
Sven

[onemorenerd]

Ich habe es mal reduziert auf den Code, der die Rekursion beeinflußt.

function recSet( $ar_pool , $int_zaehler ){
    global $int_max_item;
    $int_zaehler++;
    
    // hier ein Haufen Code, u.a. mit $ar_pool ...

    if( $int_zaehler >= $int_max_item){
        return;
    }else{
        recSet( $ar_pool , $int_zaehler );
    }
}

$int_max_item=2000;
// $int_ct_stern ist die Anzahl * in einem String.
for($x=0; $x<$int_ct_stern; $x++) $ar_pool[$x]=0;

recSet($ar_pool,0); 

Und nun bau doch bitte mal ein echo $int_zaehler; vor dem IF ein.

Kennst du eigentlich count_chars()?

[s.heinrich]

Hallo,

nach deinem Beispiel bricht das Script nach "1012" ab.
Egal, ob IE oder Firefox (aktuelle Versionen).
Testsystem: Win XP Pro + XAMPP (aktuell); RAM 4GB; TIMOUT: 60s

(...uups - wollte noch nicht senden)

Wo liegt das Prob.?

count_chars()? Jetzt kenn ich's ;-)

Grüße,
Sven

[s.heinrich]

...Nachtrag:

Ich habe gerade das nicht abgeschlossene Script aufgerufen, ins Error-Logfile gesehen und folgende Einträge zu meinem Script gefunden:

[Sun Jun 03 21:00:18 2007] [notice] Parent: child process exited with status 3221225477 -- Restarting.
[Sun Jun 03 21:00:18 2007] [crit] (22)Invalid argument: unable to replace stderr with error_log
[Sun Jun 03 21:00:18 2007] [crit] (2)No such file or directory: unable to replace stderr with /dev/null
[Sun Jun 03 21:00:18 2007] [notice] Apache/2.2.4 (Win32) DAV/2 mod_ssl/2.2.4 OpenSSL/0.9.8d mod_autoindex_color PHP/5.2.1 configured -- resuming normal operations
[Sun Jun 03 21:00:18 2007] [notice] Server built: Jan 30 2007 12:11:56
[Sun Jun 03 21:00:18 2007] [notice] Parent: Created child process 21752
[Sun Jun 03 21:00:19 2007] [notice] Child 21752: Child process is running
[Sun Jun 03 21:00:19 2007] [notice] Child 21752: Acquired the start mutex.
[Sun Jun 03 21:00:19 2007] [notice] Child 21752: Starting 250 worker threads.
[Sun Jun 03 21:00:19 2007] [notice] Child 21752: Starting thread to listen on port 443.
[Sun Jun 03 21:00:19 2007] [notice] Child 21752: Starting thread to listen on port 80.

Ich kanns nicht nachvollziehen. Wo ist der Haken?
Vielen Dank,
Sven

[s.heinrich]

Hallo,

nach dem ich bei einem versierten Systembetreuer nachfragte, gab er mir Recht:

ICH: ...oder sehen Sie sogar die 4000 items? Vielleicht liegts an meinem System (Browser)?
ER: Das gleiche Problem habe ich hier auch. Sowohl mit IE, als auch mit Firefox. Manchmal zeigt er mir bis Zeile 1059 was an, mal bis 2083 und manchmal reloaded der Browser auf "Webseite kann nicht angezeigt werden".

ICH: Was steht im error_log?
ER: Rein gar nichts! Keine Fehlermeldung oder ähnliches.

ICH: Kennen Sie solch ein Problem?
ER: Ist mir bisher noch nicht aufgefallen. Einige Applikationen die wir entwickelt haben, schmeissen bis zu 15000 Zeilen im Webbrowser ohne Probleme aus. Daher scheint es irgendetwas im Code zu sein, was dieses Verhalten aufwirft.

Läuft das ausführliche Script überhaupt bei jemanden bis zum Ende durch?

Danke und Grüße,
Sven

[pekka]

Hmm. In der lokalen Testumgebung (Apache 2, PHP 4) erscheint kurz die Liste, und daraufhin "die Verbindung wurde zurückgesetzt, während die Seite geladen wurde". Im Apache-Errorlog steht dann dieselbe Meldung wie bei Dir.

In der Debugsession der PHP-IDE, die pHP 5.2 benutzt, läuft es bis zum Ende durch (2000).

Am Besten mal die Google-Ergebnisse zur Fehlermeldung (322... usw) durchforsten.

[s.heinrich]

Hallo,

das Problem wurde zwar nicht gelößt, aber der Weg zum Ziel ist nun leider ein anderer. Es ist nicht das, was ich wollte... aber wenigstens gehts auf die Weise.
Bitte fragt mich nicht, warum es mit einer while-Schleife geht und eine rekursive Funktion scheitert, denn nichts anderes habe ich getan (tun müssen).

Offensichtlich ein Apache-Bug
So werden alle Items angezeigt:

<?php
error_reporting(E_ALL);

function countChar($str,$search){
    if(trim($str)==false || !strstr($str,$search))return 0;
    $zeichen = array();
    for ($i=0; $i<strlen($str); $i++)
        if(isset($zeichen[$str{$i}]))$zeichen[$str{$i}]++;
        else $zeichen[$str{$i}]=1;
    return $zeichen[$search];
}
function printItem($str,$int){
    echo "<code>($int) $str</code><br>\n";
    return true;
}

//*** DEFINIERE ***
$int_max_item=4000;
$str_word='a*b*c*d';// (*) Zeichen werden ersetzt (egal, wie viele)
$int_ct_stern = countChar($str_word,'*');//Anzahl Zeichen
$ar_abc=array('ä','ö','ü','ß','+','-','a','b','c','d','e'
    ,'f','g','h','i','j','k','l','m','n','o'
    ,'p','q','r','s','t','u','v','w','x','y','z');//Pool an Zeichen
//$ar_pool defin., $ar_pool[$x]=Wert, Wert wird rekur. hochgezählt
//oder ggf. zurückgesetzt
for($x=0; $x<$int_ct_stern; $x++)$ar_pool[$x]=0;
$int_ct_abc   = count($ar_abc);//Anzahl Zeichen
$int_last_x   = $int_ct_stern-1;// letzter Schlüssel
$int_zaehler  = 0;

//*** PRINT INFO ***
echo "<p><b>$int_ct_stern</b> Sternchen gefunden.<br>
    <b>$int_ct_abc</b> Zeichen stehen zur Verfügung.<br>
    Das enstpricht <b>".number_format(bcpow($int_ct_abc,$int_ct_stern,0),0,'','.')
    ."</b> Möglichkeiten<br>
    <b>$int_max_item</b> Einträge sollen ausgegeben werden.</p>\n";

//*** START ***
while ( $ar_pool[0] < $int_ct_abc ) {
    // 1. Prüfung der Werte (Testlauf)
    // 2. Ersetzen der Sternchen und Ausgabe
    // 3. In jedem Durchlauf wird ein Satz an Zeichen für das Ersetzen 
    //    der Sternchen im nkommenden Durchlauf erzeugt
    //    (Anzahl entspr. der Sternchen).
    $int_zaehler++;
    $str_word2=$str_word;//Kopie vom Orig.
    $ar_curr_abc=array();//Werte für 1 Einsatz
    //So oft wie Sternchen vorhanden das Array 
    //mit den zugewiesenen Zeichen durchlaufen
    //Werte Prüfen und Zeichen in curr_abc für das folgende Ersetzen def.
    for($x=0; $x<$int_ct_stern; $x++){
        if(!isset($ar_pool[$x]))die(" ERROR #".__LINE__." [$x] ");
        if($ar_pool[0]>=$int_ct_abc)return;//die(" Pool Ende erreicht ");
        if($ar_pool[$x] == $int_ct_abc)die(" ERROR #".__LINE__." ");
        if(!isset($ar_abc[$ar_pool[$x]]))die(" ERROR #".__LINE__." ");
        $ar_curr_abc[$x]=$ar_abc[$ar_pool[$x]];//zeichen def.
    }
    //Curr Zeichensatz verarbeiten
    foreach($ar_curr_abc as $k => $v){
        $t=strpos($str_word2,'*');
        $str_word2{$t}=$v;
        if(strpos($str_word2,'*')===false)
            if(printItem($str_word2,$int_zaehler)==false)
                die(" ERROR #".__LINE__." ");

    }
    //Neuen durchlauf vorbereiten
    //Rückwärts aktualisieren
    //Letzter zählt immer weiter, andere nur wenn Vorgänger Reset
    $ar_reset=array();//Hilfs-Array, ob 0 im Vorg. wirklich aus einem Reset erfolgte
    for($x=$int_last_x; $x >= 0; $x--){
        if( $ar_pool[$x]+1 == $int_ct_abc && $x!=0 
            && ($x==$int_last_x || isset($ar_reset[$x+1]))){
            $ar_pool[$x]=0;//Reset
            $ar_reset[$x]=true;
        
        //nur beim letzten immer +1, sonst nur wenn Vorgänger Reset
        }elseif( $x==$int_last_x || $x!=$int_last_x 
            && ($ar_pool[$x+1])==0 && isset($ar_reset[$x+1])){
            $ar_pool[$x]++;
        }
    }
    //Ende, wenn Grenzwert für Ausgabe erreicht
    if( $int_zaehler >= $int_max_item)break;
}
echo '<div style="height:300px"></div>';//Space
?>

Viele Grüße und danke an die, die mir antworteten,
Sven

[s.heinrich]

Abschließend noch eine Info dazu, warum es mit der While-Schleife funzt:
Zitat von einem Guru:

Es liegt an der rekursiven Funktion: Jeder Aufruf bewirkt eine Reservierung von Speicher im sog. Stack. Sichtbar ist hierbei immer nur die oberste Stackebene. Dieser Stack muss sich mit dem eigentlichen Programm (also dem Script und dem Parser mod_php) den Speicher teilen. Würde man sich das Ganze mit einem Debugger ansehen, würde man feststellen, dass der Speicherbedarf nicht linear, sondern zyklisch anwächst.

Es wird mit jedem Zyklus (rekursivem Aufruf) nicht nur die Funktion, sondern auch das Ergebnis samt Variablen der Funktion abgelegt.

PHP ist nun so ausgelegt, dass es "selbständig" nach einer Weile feststellt (oder glaubt festzustellen), wenn ein rekursiver Aufruf in einer Endlosschleife enden würde, da keine Abbruchbedingung innerhalb der Rekursivfunktion hinterlegt ist. Und genau das ist der Knackpunkt:

Je nach Auslastung des Speichers begrenzt PHP die Durchläufe einer solchen rekursiven Funktion. Laut B. sollte man bei mehr als 500 rekursiven Aufrufen auf Iterationen umsteigen (also while, for-next, do-until, etc.), da diese bei solchen Mengen bis zu 800% schneller abgearbeitet werden, als rekursive Aufrufe einer Funktion.

PS: Das Thema kann geschlossen werden.

[penizillin]

der code aus dem ersten(rekursiven) beispiel läuft bei mir problemlos durch und gibt 2000 einträge aus.

... würde man feststellen, dass der Speicherbedarf nicht linear, sondern zyklisch anwächst.

und zyklisch kann nicht linear sein? ich weiß nicht, warum an hier der speicher verschwendet werden soll, $ar_pool wird doch nicht groß?

PHP ist nun so ausgelegt, dass es "selbständig" nach einer Weile feststellt (oder glaubt festzustellen), wenn ein rekursiver Aufruf in einer Endlosschleife enden würde, da keine Abbruchbedingung innerhalb der Rekursivfunktion hinterlegt ist.

wo kann man das nachlesen? davon höre ich zum ersten mal.

Laut B. sollte man bei mehr als 500 rekursiven Aufrufen auf Iterationen umsteigen (also while, for-next, do-until, etc.), da diese bei solchen Mengen bis zu 800% schneller abgearbeitet werden

woher kommen diese zahlen?

p.s. Apache/2.2.4 (Unix) + PHP 5.2.1

[s.heinrich]

Hallo,

ja, 2000 klappt vielleicht noch, aber verusch mal das doppelte oder dreifache...
Rekursiv wirds dann bald nicht mehr funzen, mit while() gehts aber trotzdem locker weiter.

wo kann man das nachlesen? davon höre ich zum ersten mal.

Eben, ich auch nicht (bislang) und im Netz habe ich darüber auch nichts gefunden. Nur User, die ein ähnliches Prob. hatten und keine Hilfe. Die Email habe ich 1:1 kopiert
(Author: ein Redakteur einer PHP-Fachzeitschrift).

woher kommen diese zahlen?

Es ist evtl. ein geschätzter Wert, der die Aussage unterstreichen soll. Ich weiß es nicht, aber dessen Aussage deckt sich mit meiner kürzlich gewonnenen Erkenntnis. ;-)

Viele Grüße,
Sven