Rekursive Funktion wird nicht verlassen

[Hakan]

Hallo Leute,

also ich hab da ein Problem, hoffenltich könnt ihr mir da weiter helfen. Hab schon viel zu viel Zeit damit vergeudetet.

Ich habe eine Baumstruktur, dass ich durchsuchen möchte.
Sobald der gesuchte Knoten gefunden wird, soll der Knotgen zurückgegeben werden und die Funktion verlassen - also eine stinknormale rekursive Tiefensuche.

Die Funktion sieht folgendermaßen aus:

function findNode($rootnode, $searchnodeid){
 if($rootnode->getId() == $searchnodeid){
                echo "gefunden";
  return $rootnode;
 }else{
  $childarray = $rootnode->getSubnodes();
  foreach($childarray as $nextnode){
   echo $nextnode->getId()."-".$searchnodeid."|";
   findNode($nextnode, $searchnodeid);
  }
 }
}

Bei Testbildschirmausgaben stelle ich fest, dass in die If-Abfrage richtig funzt. Also der Text "gefunden" wird ausgegeben, aber der return funzt nicht und der Baum wird weiter durchlaufen, bis am Ende  null zurück gegeben wird.

Warum funzt return $rootnode nicht??

Danke allen in Voraus!

Gruß

Hakan

[dedlfix]

echo $begrüßung;

foreach($childarray as $nextnode){
   findNode($nextnode, $searchnodeid);
  }

Warum funzt return $rootnode nicht??

Ein return beendet nur den aktuellen Funktionsaufruf. Du beendest also das in der Schleife aufgerufene findnode(), aber das davon zurückgegebenen Ergebnis ignorierst du. Danach geht es mit dem nächsten foreach-Durchlauf weiter.

echo "$verabschiedung $name";

[Hopsel]

Hi Hakan!

function findNode($rootnode, $searchnodeid){
if($rootnode->getId() == $searchnodeid){
                echo "gefunden";
  return $rootnode;
}else{
  $childarray = $rootnode->getSubnodes();
  foreach($childarray as $nextnode){
   echo $nextnode->getId()."-".$searchnodeid."|";
   findNode($nextnode, $searchnodeid);
  }
}
}

Bei Testbildschirmausgaben stelle ich fest, dass in die If-Abfrage richtig funzt. Also der Text "gefunden" wird ausgegeben, aber der return funzt nicht und der Baum wird weiter durchlaufen, bis am Ende  null zurück gegeben wird.
Warum funzt return $rootnode nicht??

Weil du den Rückgabewert nicht durchreichst.
"return findNode($nextnode, $searchnodeid);" wäre richtig.

MfG H☼psel

[GodLike]

Hallo Leute,

also ich hab da ein Problem, hoffenltich könnt ihr mir da weiter helfen. Hab schon viel zu viel Zeit damit vergeudetet.

Ich habe eine Baumstruktur, dass ich durchsuchen möchte.
Sobald der gesuchte Knoten gefunden wird, soll der Knotgen zurückgegeben werden und die Funktion verlassen - also eine stinknormale rekursive Tiefensuche.

Die Funktion sieht folgendermaßen aus:

function findNode($rootnode, $searchnodeid){
if($rootnode->getId() == $searchnodeid){
                echo "gefunden";
  return $rootnode;
}else{
  $childarray = $rootnode->getSubnodes();
  foreach($childarray as $nextnode){
   echo $nextnode->getId()."-".$searchnodeid."|";
   findNode($nextnode, $searchnodeid);
  }
}
}

Bei Testbildschirmausgaben stelle ich fest, dass in die If-Abfrage richtig funzt. Also der Text "gefunden" wird ausgegeben, aber der return funzt nicht und der Baum wird weiter durchlaufen, bis am Ende  null zurück gegeben wird.

Warum funzt return $rootnode nicht??

Danke allen in Voraus!

Gruß

Hakan

Du solltest vielleicht in der foreach eine If-Abfrage einbauen.
Wenn findNode was zurückgibt beenden, ansonsten weiter.
Dann sollten sich alle Funktionsaufrufe beenden.

GodLike

[Hopsel]

Hi GodLike!

Du solltest vielleicht in der foreach eine If-Abfrage einbauen.

Wozu? Die Abbruchbedingung ist schon definiert.

Wenn findNode was zurückgibt beenden, ansonsten weiter.

Wie gesagt...

Dann sollten sich alle Funktionsaufrufe beenden.

Ob er den Rückgabewert in der foreach-Schleife in einem weiteren If-Konstrukt abfragt, ist völlig belanglos; wichtig ist, _dass_ er ihn beachtet.

MfG H☼psel

[Harlequin]

Yerf!

Hi GodLike!

Du solltest vielleicht in der foreach eine If-Abfrage einbauen.
Wozu? Die Abbruchbedingung ist schon definiert.

Die Abbruchbedingung ist eine gefundene Node, die Funktion kann aber auch NULL zurückliefern, wenn sie nichts findet. In diesem Fall sollte die foreach-Schleife mit dem nächsten Element weitermachen. Natürlich muss hier eine Unterscheidung (if) rein...

Gruß,

Harlequin

[Hakan]

Yerf!

Hi GodLike!

Du solltest vielleicht in der foreach eine If-Abfrage einbauen.
Wozu? Die Abbruchbedingung ist schon definiert.

Die Abbruchbedingung ist eine gefundene Node, die Funktion kann aber auch NULL zurückliefern, wenn sie nichts findet. In diesem Fall sollte die foreach-Schleife mit dem nächsten Element weitermachen. Natürlich muss hier eine Unterscheidung (if) rein...

Gruß,

Harlequin

Ihr habt alle Recht!
Wenn ich eine Funktion aufrufe, muss ich natürlich auch den Rückgabewert berücksichtigen.
Ich wusste, dass es ein Leichtsinnsfehler ist. Ist jedesmal so, wenn ich lange an einem Problem nage.

Danke für alles!

Gruß, Hakan

[Tom]

Hello,

meinen Senf kann ich hier nicht für mich behalten...

bei rekursiven Funktionen im Umfeld einer strukturierten Programmiersprache sollte man aus Gründen der Performance für das Such-Ergebnis eine Referenz durchreichen.

Als Rückgabewert und damit "Laufbedingung der Rekursion" sollte man möglichst nur True oder False zurückgeben, oder einen ähnlich wenig komplexen Vergleich (sogenannter Index-Vergleich).

Das verkürzt die Laufzeit erheblich.

Den Rückweg kann man sich leider nicht generell schenken, weil oft noch Handles zurückgegeben werden müssen oder explizit Speicher freigegeben werden muss.

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[Tom]

Hello,

Als Rückgabewert und damit "Laufbedingung der Rekursion" sollte man möglichst nur True oder False zurückgeben, oder einen ähnlich wenig komplexen Vergleich (sogenannter Index-Vergleich).

Sollte sinngemäß heißen:
Als Rückgabewert und damit Vergleichswert für die "Laufbedingung der Rekursion" sollte man möglichst nur True oder False zurückgeben, oder einen ähnlich einfachen Wert, der keinen  komplexen Vergleich notwenig macht. Ein numerischer Wert für einem sogenannten Index-Vergleich, wäre nach BOOLEAN der nächst schmerzloseste.

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[dedlfix]

echo $begrüßung;

bei rekursiven Funktionen im Umfeld einer strukturierten Programmiersprache sollte man aus Gründen der Performance für das Such-Ergebnis eine Referenz durchreichen.

Und du bist sicher, dass das Anlegen einer Referenz zeitsparender ist, als PHPs Eigenart, eine echte Kopie nur dann anzulegen, wenn der Inhalt zweier Variablen sich zu ändern anfängt?

In der Beschreibung zu debug_zval_dump() hängt ein Link zu einem Dokument namens References Explained von Derick Rethans, das PHPs Variablen-Handling beschreibt.
Auch rät das Kapitel Returning References vom Gebrauch von Referenzen aus Performancegründen ab.

echo "$verabschiedung $name";