PHP + rekursion

[Kinman]

Hi, ich hab ein Problem. Und zwar möche ich mir eine Art Routefinder programmieren.. nur leider scheiterts bei mir schon ganz am Anfang, nämlich an der Rekursion.

Folgende Funktion bringt immer einen Internal Server Error (500):

function bestRoute($start, $end, $hops, $route)
{
for($i = 2; $i < 80; $i++)
{
if (isset($route[$start][$i]))
{
if ($i == $end)
{
return $hops;
}
else if($i != $start)
{
$hops = bestRoute($i,$end,$hops,$route);
}
}
}
echo($hops);
}


nehme ich die Rekursion heraus, funktioniert die Funktion, bzw. es gibt keinen Server error.
Das Array ist momentan auch so, das es zu keiner Endlosschleife kommen kann!

Weis jemand Rat?

mfg Kinman

[MeLLe]

Vielleicht kommst du mit deiner Rekursion an die Grenzen der Umgebung?

Siehe dazu hier (http://bugs.php.net/bug.php?id=1901).

[Gast]

Ich könnte mir vorstellen, daß das ein TimeOut darstellt - PHP Scripte dürfen ja nur eine gewisse Zeit ausgeführt werden. Wenn sie nach x Sekunden nicht fertig sind, werden sie gnadenlos gekillt.

Gib doch mal $i aus direkt vor dem rekursiven Aufruf

[Kinman]

Das Script braucht nicht mal eine Sekunde, es passiert nichts, außer das ich eine dicke Fehlermeldungbekomme (Internal Server Error 500).
Ich kann auch nichts ausgeben, da nichts angezeigt wird.
Habs auch mit max. 5 Stufen versucht --> Selbiges

mfg Kinman

[Marscel]

Ich weiß jetzt nicht, obs daran liegt, aber die Funktion hat kein return (es sei denn, echo() kann man auch dazu missbrauchen), also wird kein Wert auf $hops übergeben.

[Kinman]

Stimmt, sie returned nicht immer was, aber ich habs korrigiert und es ist noch immer das selbe :(

mfg Kinman

[Expandable]

Sieht mir irgendwie sehr nach einer Endlosschleife aus. Was übergibst Du denn für $end? Kann $end überhaupt jemals von $i erreicht werden? Wenn es das erreicht, wann hören die vorherigen Loops auf??

[Kinman]

$end ist immer < 80.
Ich habe jetzt ein altes Programm aus Java umgeschrieben (zum testen). Funktioniert auch net...
Es ist ein Programm zum durchlaufen von Baumstrukturen, also relativ einfach.
Ich denke ich werde mir etwas überlegen um das Problem ohne Rekursion zu lösen.

mfg Kinman

[Expandable]

Hab das jetzt mal mit folgendem Code gestestet:


function bestRoute($start, $end, $hops, $route)
{
for($i = 2; $i < 80; $i++)
{
if (isset($route[$start][$i]))
{
if ($i == $end)
{
return $hops;
}
else if($i != $start)
{
$hops = bestRoute($i,$end,$hops,$route);
}
}
}
echo($hops);
}

$route = array();
for ($i = 0; $i < 80; $i++)
{
for ($j = 0; $j < 80; $j++)
{
$route[$i][$j] = 'r';
}
}

bestRoute(6, 70, 'test', $route);

Firefox spuckt einen "Document Contains No Data"-Fehler aus.

Es könnte aber wirklich eine Endlosschleife sein - bei rekursiven Funktionen muss man da höllisch aufpassen. Also z.B.:

Der erste Aufruf von bestRoute(). $i wird zu zwei, es geht los. Der Wert in $route existiert, da $i != $end ist und !=$start ist, wird bestRoute() das nächste mal aufgerufen.

$i wird 2, ist aber gleich $start, also passiert nichts weiter. Bei $i = 3 wird bestRoute() wieder aufgrufen. Das Problem ist nun: $start wird also jedes Mal um 1 erhöht. Ist start wieder 6, so geht die Schleife praktisch wieder komplett von vorne los, das hatten wir ja schon eigentlich -> Endlosschleife. Bei $start = 6 startet das Ding wieder von vorn.

[Drexel]

Stimmt, sie returned nicht immer was, aber ich habs korrigiert und es ist noch immer das selbe :(

mfg Kinman

Poste bitte nochmal mit Korrektur. Habe gerade auch 2 rekursionen in PHP zum Auslesen von Baumstrukturen hinter mir. Bin also noch warm und kann dann evtl helfen ;)