result nicht gesetzt (rekursive Tiefensuche)

[wunderkinnd]

Ich habe hier einen funktionierenden ALgorithmus der Tiefensuche. Er arbeitet rekursiv und durchläuft einen Graphen (mit den selbsterklärenden Methodennamen - hoffe ich). Der Algorithmus findet nicht die optimale Lösung (Weg von Knoten start zu Knoten ziel) aber er findet zumindest eine Lösung.

Meine Frage lautet eher: Warum funktioniert das Ganze?

Delphi-Quellcode:

//-------- tiefensuche (public) ----------------------------------------
function TGraphAlgorithms.tiefensuche (graph: TGraph; start: TGraphNode; ziel: TGraphNode; weg: String) : String;
  var l : TList;
begin
  start.mark;
  if start.getName = ziel.getName then
    result := weg
  else
  begin
    l := graph.getNeighbours(start);
    l.toFirst;
    while l.hasAccess do
    begin
      if NOT (l.getObject as TGraphNode).isMarked then
        result := tiefensuche(graph, (l.getObject as TGraphNode), ziel, weg + (l.getObject as TGraphNode).getName);
      l.next;
    end;
  end;
end;

Genauer gesagt: Was genau hat eine Methode für einen Wert, wenn result nicht gesetzt wird? Warum wird result (wenn einmal eine Lösung gefunden wurde) nicht immer wieder mit NIL oÄ überschrieben?

[Dalai]

Zitat von wunderkinnd:

Was genau hat eine Methode für einen Wert, wenn result nicht gesetzt wird?

Die Frage ist zu allgemein formuliert, aber in deinem Fall (Funktionsrückgabe als String) ein Leerstring, also '' , jedenfalls dann, wenn man nicht explizit einen anderen Wert zuweist.

Zitat:

Warum wird result (wenn einmal eine Lösung gefunden wurde) nicht immer wieder mit NIL oÄ überschrieben?

Ganz einfach: Rekursion arbeitet so. Es wird ja erst das Ergebnis gaaaanz unten ermittelt, bevor der Stapel wieder rückwärts abgearbeitet, d.h. die Ergebnisse dann an Result zugewiesen werden. Oder anders ausgedrückt: Result hat für jeden einzelnen Funktionsaufruf eine eigene Speicheradresse und ist damit verschieden von "anderen" Results.

Vermutlich hab ich das jetzt nicht besonders gut und evtl. sogar falsch erklärt .

MfG Dalai

[himitsu]

Du hast da einen "zufällig" funktionierenden Code.
Wenn man diese Funktion mehrfach in einer Schleife aufruft, dann wirst du dich womöglich wundern, daß es nicht immer funktioniert.
Deswegen warnt dich ja auch der Compiler davor.

Geh doch mal deinen Code durch und schau, ob dem Result wirklich immer etwas zugewiesen wird.
Tipp: Was passiert wohl, wenn in der Schleife das IF niemals zutrifft?

[wunderkinnd]

Hallo und Danke für die Antwort, aber das genau ist mein Problem:

zum ersten Kommentar: ich verstehe schon, warum der Algorithmus funktioniert, wenn etwas sinnvolles gefunden wird. Das Prinzip der Rekursion ist mir schon klar. Schließlich stammt der Code ja auch von mir

Der Code funktioniert tatsächlich aber auch, wenn die erste if-Abfrage nicht zutrifft. Dann wird halt ein leerer String zurückgegeben.

Das ist aber das Problem. Wenn nämlich eine Funktion, deren result-Wert nicht belegt wird zu einem leeren String '' ausgewertet wird, dann müsste doch eine einmal gefundene Lösung letztendlich überschrieben werden, wenn weitere Nachfolger gefunden werden, oder?

Konkret folgender Graph:

A - B
|
C

Gesucht ist der Weg von A nach B. Nun werden ja REKURSIV alle noch unbesuchten Nachfolger von A untersucht.
Zuerst wird A B untersucht, Lösung "AB" wird als String an result zugewiesen.
Nun wird aber noch AC überprüft, es wird keine Lösung gefunden, result wird also NICHT belegt und nun wird in der aufrufenden Methode, in welcher result ja noch der Wert "AB" hat dieser Wert mit NICHTS bzw. '' oder auch NIL überschrieben.
Insgesamt müsste dann die Methode doch auch NIL oder '' ausgeben, oder? Tut sie aber nicht, denn sie liefert korrekterweise "AB" zurück.

Ich hoffe, das war soweit verständlich ausgedrückt.

[himitsu]

Zitat:

Der Code funktioniert tatsächlich aber auch, wenn die erste if-Abfrage nicht zutrifft. Dann wird halt ein leerer String zurückgegeben.

Es wird eben nur zufällig ein Leerstring zurückgegeben, da du nicht explizit einen Leerstring zuweist.

Du mußt grundsätzlich davon ausgehen, daß ein Result niemals initialisiert ist.
Bei Strings, Interfaces und dynamischen Arrays ist meisten zufällig ein '' zugewiesen, da diese Typen eine automatische Speicherverwaltung besitzen und demnach automatisch vom Delphi initialisiert werden.

Allerdings werden diese Results (String, Interface und dyn. Array) intern nicht als Result-Parameter behandelt, sondern werden als VAR-Parameter.
Die Initialisierung deines Strings befindet sich außerdem nicht in deiner Funktion, sondern beim Aufrufer, bzw. da, woran das Result zugewiesen wird, was eben bei mehrfachen Aufrufen, z.B. in einer Schleife zu Problemen führt, da diese Stringvariable nur einmal zu Beginn initialisiert wird und nicht bei jedem Aufruf.

Hier würdest du doch bestimmt x in der MessageBox erwarten?
Ich allerdings nicht.

Delphi-Quellcode:

function Test: string;
begin
  Result := Result + 'x';
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  i: Integer;
  S: string;
begin
  for i := 1 to 10 do
    S := Test;
  ShowMessage(S);
end;

[wunderkinnd]

Hallo,

ich befürchte, wir reden aneinander vorbei. Hier ein einfacheres Beispiel:

Delphi-Quellcode:

function TGraphTool.test (s : integer): String;
begin
  if s > 5 then result := '6';
  if s < 5 then begin
    result := test(6);
    result := test(5);
  end;
end;

Ich verstehe nicht, warum beim Aufruf

showMessage(test(4));

tatsächlich '6' ausgegeben wird und nicht etwa '' oder NIL oder so.

[himitsu]

Finde ich nicht, denn du hörst nicht zu.

Hier sollte ebenfalls wieder mindestens 1 Compilerwarnung auftauchen.
- Rückgabewert nicht initialisiert (bei s = 5)
- zugewiesener Wert wird nicht benutzt (das erste result := ..., im s < 5)

Und genau deswegen kommt hier 6 raus, weil DU nichts initialisierst, denn sonst würde ein Leerstring aus deiner Funktion rauskommen.

Es wird Test mit 4 Aufgerufen, also landet die Ausführung im S < 5.
Dadurch wird dann erstmal Test mit 6 aufgerufen, was über S > 5 eine "6" liefert,
danach dann nochmal Test mit 5, was "nichts" zurückliefert, aber da DU schonwieder vergessen hast das Result zu initialisieren und Aufgrund der von mir vorhin beschiebenen Eigenschaft von aufeinanderfolgenden Aufrufen, und Zuweisung auf die selbe Variable, wird die vorher gesetzte "6" nicht mit einem neuen Result "überschrieben".

Außerdem empfehle ich dir dringend die Benutzung des Debuggers.