Rekursion abbrechen

[Untitled]

Ich stehe vor einem kleinem Designproblem in Zusammenhang mit Rekursion. Folgender Code:

classMember = 0;

someFooBarFunc(){

  //some Queue operations

  for ( ... )
    if (foo == SOME_VALUE){
      classMember = ...;
      return;
    }

    //...
    someFooBarFunc();
  }

}

Ich befinde mich in einer beliebigen Rekursionstiefe. Wie kann ich nun einfach mittendrin abbrechen? Das Problem ist, dass die Rekursion in einer Schleife aufgerufen wird. Dadurch bringt ein einfaches return nichts. Dadurch verläßt er nur die eine Rekursionsstufe und macht in der nächsthöheren in der Schleife munter weiter.

Ein Lösungsansatz wär folgender:

resultFound = false;
classMember = 0;

someFooBarFunc(){
  if (resultFound)
    return;

  //some Queue operations

  for ( ... )
    if (foo == SOME_VALUE){
      classMember = ...;
      resultFound = true;
      return;
    }

    //...
    someFooBarFunc();
  }

}

Ich setzte einfach ein Flag. Ist dieses Flag gesetzt, breche ich jede Funktion am Anfang gleich ab.

Gib es elegantere Lösungen für dieses Problem?

[CStoll]

brauchst du an der Stelle überhaupt eine Rekursion? Ich würde (so wie ich deinen Codefetzen sehe) eher eine Schleife verwenden:

void someFunc()
{
  while(true)
  {
    //...
    if(foo==SOME_VALUE)
    {
      //write output
      return
    }
    //...
  }
}

[Untitled]

Ich versuche es mal das Problem etwas besser zu beschreiben.

Es handelt sich dabei um einen Graphen, in dem ich einen Knoten finden will. Dazu muss ich für jeden Knoten jeden Weg ausprobieren(Breitensuche).

In einer Schleife gehe ich für den aktuellen Knoten alle mit ihm verbundenen Knoten durch. Handelt es sich bei dem aktuellen Knoten in der Schleife nicht um einen Treffer, muss ich für diesen Knoten wieder den selben Schritt ausführen(hier kommt die Rekurion ins Spiel).

Sobald ich den gesuchten Knoten gefunden habe, breche ich die Rekursion ab.

Hoffe diese Erklärung ist etwas besser.

[groovemaster]

Untitled schrieb:

Gib es elegantere Lösungen für dieses Problem?

Durchaus, versuch für deine Rekursion ein iteratives Äquivalent zu finden. Dieses kannst du auf den einzelnen Ebenen besser kontrollieren. break, continue, return und selbst goto helfen dir dabei.

[camper]

eine weitere alternative wäre, exceptions zu benutzen. der erste funktionsaufruf muss dann in einen try-block. ob dass günstiger als eine iterative lösung ist, kann ich hier nicht beurteilen; es hat jedenfalls den vorteil, dass es weniger änderungen am code verlangt, falls dieser bereits exception-sicher ist.

[123456789]

...und selbst goto helfen dir dabei

Na dann doch lieber rekursion

Eigentlich ist doch der zweite vorschlag von dir nicht so schlecht, vielleicht resultFound als return wert zurückgeben. Und wenn Du das sauber machst, dann brauchst du das erste

if (resultFound)
    return;

auch nicht.

[Nidhogger]

Untitled schrieb:

Dazu muss ich für jeden Knoten jeden Weg ausprobieren(Breitensuche).

Breitensuche sucht ja normalerweise nach dem kürzesten Weg und nicht - wie die Tiefensuche - nach e i n e m Weg. Breitensuche prüft erst alle Wege der Länge 1, dann alle der Länge 2, etc. und wird normalerweise mit ner Queue implementiert.

Nid

[Apollon]

Breitensuche sucht nicht nach Wegen und Threadsteller auch nicht.

[Nidhogger]

Apollon schrieb:

Breitensuche sucht nicht nach Wegen und Threadsteller auch nicht.

Breitensuche wird zur Suche des kürzesten Wegs/Pfads benutzt. Auch wenn hier keine Wege gesucht werden, ist die übliche Implementierung einer Breitensuche mit Queue und nicht Rekursion.

Nid

[Untitled]

Ersteinmal vielen Dank an alle!

@Nidhogger: Ich wollte zuerst auch die Breitensuche mit Hilfe einer Queue implementieren, hatte dabei aber keine Möglichkeit gefunden wie ich alle Knoten von Start bis Ziel der Reihenfolge nach speichern kann, ohne dafür extra eine weitere Liste zu benutzen oder die Konten zu verändern. Welche Möglichkeiten übersehe ich?

Mein Pseudocode würde dafür so aussehen:

füge Startknoten in Queue
while (Queue ist nicht leer)
  hole Element aus Queue
  for (alle Kanten von aktl. Knoten)
    if (Kante noch nicht besucht)
       Füge Kante in Queue ein
    end if
  end for
end while

[imhotep]

Was noch wichtig ist, dass dein Query nach FIFO funktioniert, weil sonst es keine Breitensuche wird, sondern einen Tiefensuche oder irgendein Mischmasch.

[mantiz]

classMember = 0;

bool someFooBarFunc(){ 

	for (...) {
		if (foo == SOME_VALUE) {
			classMember = ...; 
			return true;
		}
		if (someFooBarFunc()) {
			return true;
		}
	}

	return false;
}

Ist vielleicht nicht so besonders chic, aber so müsste es doch gehen, oder?

[Nidhogger]

Untitled schrieb:

@Nidhogger: Ich wollte zuerst auch die Breitensuche mit Hilfe einer Queue implementieren, hatte dabei aber keine Möglichkeit gefunden wie ich alle Knoten von Start bis Ziel der Reihenfolge nach speichern kann, ohne dafür extra eine weitere Liste zu benutzen oder die Konten zu verändern. Welche Möglichkeiten übersehe ich?

Du müsstest ja in jeden Knoten sowieso ein Attribut haben, mit dem du festhalten kannst, ob du einen Knoten bereits besucht hast. Wenn du dieses Attribut so verwendest, dass du dort abspeicherst, wie weit der Knoten vom Ursprungsknoten entfernt sind, dann brauchst du dich, nachdem du den gesuchten Knoten gefunden hast, einfach nur rückwärts an diesen Zahlen zurückzuhangeln.

Nid.

[groovemaster]

123456789 schrieb:

Na dann doch lieber rekursion

Wieso?

[123456789]

Na weils übersichtlicher ist als dieses goto gespringe.

[CStoll]

Brauchst du für dein Problem wirklich diese Graphen-Struktur? (besonders sind Graphen nicht gerade die ideale Grundstruktur für eine Suche)

[groovemaster]

123456789 schrieb:

Na weils übersichtlicher ist als dieses goto gespringe.

Uninteressant. Rekursion mag zwar übersichtlicher erscheinen, ist aber von der Logik her oftmals viel schwerer zu verstehen. Ausserdem sagt niemmand, dass du etliche goto's verwenden sollst, idR gibt es bessere Möglichkeiten. Wer aber glaubt, es führt kein Weg an goto in seinem Code vorbei, dann soll er's auch nutzen. Besser als irgendwelche Dummys einzuführen ist es allemal. Dabei zu beachten ist nur, niemals nach oben springen, denn sonst kann man tatsächlich schnell den Überblick verlieren.

[CStoll]

groovemaster schrieb:

CStoll schrieb:

Na weils übersichtlicher ist als dieses goto gespringe.

Wenn du schon zitierst, dann achte bitte darauf, wen (ich störe mich zwar nicht daran, daß mein Name genannt wird - aber bitte im richtigen Zusammenhang)

[1234567789]

CStoll schrieb:

groovemaster schrieb:

CStoll schrieb:

Na weils übersichtlicher ist als dieses goto gespringe.

Wenn du schon zitierst, dann achte bitte darauf, wen (ich störe mich zwar nicht daran, daß mein Name genannt wird - aber bitte im richtigen Zusammenhang)

groovemaster schrieb:

Uninteressant. Rekursion mag zwar übersichtlicher erscheinen, ist aber von der Logik her oftmals viel schwerer zu verstehen. Ausserdem sagt niemmand, dass du etliche goto's verwenden sollst, idR gibt es bessere Möglichkeiten. Wer aber glaubt, es führt kein Weg an goto in seinem Code vorbei, dann soll er's auch nutzen. Besser als irgendwelche Dummys einzuführen ist es allemal. Dabei zu beachten ist nur, niemals nach oben springen, denn sonst kann man tatsächlich schnell den Überblick verlieren.

Also ich hab noch keinen Code (außer Assembler) gesehen, bei dem man ein goto nicht vermeiden hätte können. Man kann natürlich jede Rekursion mit hilfe eines Stacks in ein iteratives prog. umwandeln, aber obs dann übersichtilcher ist? Man sollte natürlich nur da Rekursion verwenden wo es wirklich besser ist oder sein muss.

[imhotep]

groovemaster schrieb:

Wer aber glaubt, es führt kein Weg an goto in seinem Code vorbei, dann soll er's auch nutzen.

Oder er soll sich wohl strukturierten Code ausdenken.

[groovemaster]

CStoll schrieb:

Wenn du schon zitierst, dann achte bitte darauf, wen

Solltest vielleicht nicht soviel posten.
Lass mich mal kurz nachrechnen, 12 Tage dabei, fast 400 Beiträge, dh 33 Beiträge pro Tag. Respekt!

1234567789 schrieb:

Also ich hab noch keinen Code (außer Assembler) gesehen, bei dem man ein goto nicht vermeiden hätte können.

Natürlich kannst du immer goto vermeiden, die Frage ist nur, zu welchen Kosten. Versteh mich nicht falsch, ich bin kein Verfechter von goto. Nur ist es unsinnig sich stur gegen die Verwendung von goto zu stellen, auch wenn der aussergewöhnliche Fall eintreten sollte, dass es mal die einfachste Lösung darstellt. Es geht auch nicht darum, seinen Code möglichst so aufzubauen, dass man goto erst gar nicht braucht. Das versteht sich eigentlich von selbst.

1234567789 schrieb:

Also ich hab noch keinen Code (außer Assembler) gesehen, bei dem man ein goto nicht vermeiden hätte können.

Was allerdings nicht für die Allgemeinheit zutreffen muss.

1234567789 schrieb:

Man kann natürlich jede Rekursion mit hilfe eines Stacks in ein iteratives prog. umwandeln

Kann sein, dafür ist ein Stack aber gar nicht notwendig.

1234567789 schrieb:

aber obs dann übersichtilcher ist?

Wie bereits gesagt, bei solchen Sachen geht es in erster Linie aber nicht um Übersichtlichkeit, sondern um Codeverständnis.