Wie kann man endgültig aus einer Rekursion ausbrechen?

Diskutiere Wie kann man endgültig aus einer Rekursion ausbrechen? im Allgemeine Java-Themen Bereich.
Zrebna

Zrebna

Hi!

Erstmal folgender Codesnippet:
Java:
public boolean existsInTree(Node root, File file) {
      boolean inTree = false;
        for(Node child : root.getChildren()) {
            if(child.isLeaf()) {
                inTree = child.equals(file);
                break;
            } else {
               existsInTree(child, file);
            }
        }
        return inTree;
    }
Ich habe eine Datenstruktur, die einen Baum abbildet (root, nodes und leafs), sowie ein Arbeitsverzeichnis/Ordnerstruktur abbilden soll, wobei die leafs immer files (keine Ordner) sind.
In dieser Methhode möchte ich prüfen, ob ein übergebenes File, das in meinen Baum hinzugefügt werden soll,
schon im Baum exisitiert, oder nicht.
Wir beginnen beim traversieren ganz oben in der Wurzelnode (Hauptordner).
Hier iterieren wir durch die Kinder-Nodes dieser Node und gucken in Zeile 4, ob irgendein Kinder-Node bereits ein Leaf (Repräsenator für File) ist,
d.h. selber keine weiteren Kinder-Nodes mehr hat.
Falls das so ist, dann wird geprüft, ob diese Leaf-Node == file (gem. meiner equals()_Implementierung).
Das passt so alles und im Debugger wird dann auch das boolean Attribut 'inTree' korrekt auf true gesetzt, wenn meine equals() wahr ausgibt.
Nun würde ich am liebsten alles in dieser Methode beenden und keine weiteren rekursiven Aufrufe erlauben, dh. zurück zu der Methode springen,
die quasi diese existInTree()_Methode aufgerufen hat und dabei true zurückgeben.

Jedoch passiert das nicht und im Debugger sehe ich , dass das Programm zu Erst in die letzte Zeile "return inTree") springt (hier ist inTree noch true)
und von dort zurück in die Zeile im else-Block ("existInTree(child, file)") - hier is inTree dann wieder false,
um die existInTree()-Methode wieder rekursiv aufzurufen.

Wie kann ich das verhindern, oder zumindest den True-Wert bzgl. meiner boolean Variable so lange sichern, bis wirklich alle rekursiven Aufrufe vorbei sind und ich dann eben mit true ganz am Ende returnen kann?

PS: Weiß Jemand, wie ich es hier im Forum beim Codesnippet-Posten so anstelle, dass Zeilenangaben mit angezeigt werden?

Lg,
Zrebna
 
Zuletzt bearbeitet:
MoxxiManagarm

MoxxiManagarm

Du machst aktuell nichts mit dem Ergebnis des rekursiven Aufrufes.

Änderungsvorschlag:
Java:
public boolean existsInTree(Node root, File file) {
        for(Node child : root.getChildren()) {
            if(child.isLeaf()) {
               if (child.equals(file)) return true;
            } else {
               if (existsInTree(child, file)) return true;
            }
        }
        return false;
    }
 
Zrebna

Zrebna

Hm,
wie meinst du das?
Ich will ja einach nur überprüfen, ob sich die neu-hinzugefügte File bereits als Node in meinem Baum befindet - falls ja,
dann soll eben true returned werden und je nachdem, ob am Ende hier true oder false returned wird,
geht es in der Methode, die diese existsInTree()-Methode aufgerufen hat, eben so oder anders weiter:
Bei true:
Kommt ein System.out.Println , wie z.B. "Diese Datei kann nicht hinzugefügt werden, weil sie bereits im Baum exisitiert".
Bei false:
Wird die Node in meinen Baum hinzugefügt...

Oder missverstehe ich, was du mir sagen willst?
 
L

LimDul

Du lieferst in existsInTree einen Wert zurück, den du aber in der Rekursion verwirfst.

Erster Aufruf von existsInTree:
Ruft Rekursiv existsInTree auf (in deinem else zweig).
Dieser, zweite Aufruf gibt true zurück.
Der errste Aufruf bekommt das ergebnis, macht damit aber nix und liefert am ende den Wert inTree zurück - der weiterhin false.

Den jeder rekursive Aufruf von existsInTree hat seine eigene, lokale Variable inTree. Und nur bei dem untersten Aufruf (wo es gefunden wird), setzt du die. Die der oberen Aufrufe bleibt weiterhin immer false.
 
J

JustNobody

Das ist so natürlich Quatsch. Ich sehe auf Anhieb zwei Möglichkeiten:
a) Exception, die in der Rekursion nicht gefangen wird.
b) System.exit

Über den Sinn / Unsinn bzw. wann das ggf. anzuwenden ist. kann man natürlich diskutieren und das ist natürlich nichts, das der TE hier brauchen kann / in Betracht ziehen kann. Aber diese Möglichkeiten gibt es und damit kann man aus einer Rekursion ausbrechen.
 
Zrebna

Zrebna

Das ist so natürlich Quatsch. Ich sehe auf Anhieb zwei Möglichkeiten:
a) Exception, die in der Rekursion nicht gefangen wird.
b) System.exit

Über den Sinn / Unsinn bzw. wann das ggf. anzuwenden ist. kann man natürlich diskutieren und das ist natürlich nichts, das der TE hier brauchen kann / in Betracht ziehen kann. Aber diese Möglichkeiten gibt es und damit kann man aus einer Rekursion ausbrechen.
Ja, da war mein Threadtitel nicht optimal formuliert.

Vielen Dank speziell auch an MoxxiManagarm und LLimDul - nun ist es mir gerade klar geworden - gucke mir das direkt nochmal genauer an:)
 
Zrebna

Zrebna

Steht quasi in meinem Änderungsvorschlag
Hi!
Deine Idee hat sehr gut funktioniert - vielen Dank dafür! :)

Nun wollte ich deine Idee auch bzgl. einem anderem Problem anwenden, bei dem es darum geht,
dass eine Methode nach einer Node sucht, die bereits im Baum ist, indem sie alle Nodes mit der
potentiell hinzuzufügenden Datei abgleicht - falls diese matchen, soll diese gematchte Node returned werden.
Auch hier wird rekursiv aufgerufen - aber mein Programm geht am Ende rekursiv bis fast ganz nach oben wieder zurück,
und returned mir am Ende dementsprechend eine andere Node, als die gewünschte (beim erstem return, nach Match)

Java:
public Node searchNode(Node root, File file) {
        for(Node child : root.getChildren()) {
            if(child.isLeaf()) {
               if(child.equals(file)) { return child; }
            } else {
                if(findNode(child, file) != null) {
                    return child;
                }
            }
        }
        return null;
    }
Ich müsste ja eigentlich meine gematchte Node in dem rekursivem Aufruf nach else zurückgeben und dann immer wieder erneut zurückgeben.
Wie stelle ich das hier an?
 
MoxxiManagarm

MoxxiManagarm

Java:
if(findNode(child, file) != null) {
                    return child;
                }
Du returnst hier child und nicht den rekursiv gefundenen leaf.

Änderungsvorschlag:
Java:
public Node searchNode(Node root, File file) {
        for(Node child : root.getChildren()) {
            if(child.isLeaf()) {
               if(child.equals(file)) { return child; }
            } else {
                Node found = findNode(child, file);
                if(found != null) {
                    return found;
                }
            }
        }
        return null;
    }
 
H

handshake45

Aber diese Möglichkeiten gibt es und damit kann man aus einer Rekursion ausbrechen
Er möchte sicher nach dem rekursiven Aufruf noch etwas tun, da ist ein System.exit(0) nicht geeignet. Seine Frage bezog sich speziell darauf ,den rekursiven Stack abzubrechen, und das geht nicht, ohne alle Methoden in umgekehrter Reihenfolge zu verlassen.

Ich sehe leider auch nur die Möglichkeit, sauber zu programmieren.
 
J

JustNobody

Das das Problem vom TE einer saubere Lösung bedarf, ist ja klar. Diesbezüglich hatten Moxxi und LimDul ja auch entsprechend geantwortet.

Da hat mich Deine Antwort etwas gewundert, da sie diesbezüglich nichts zur Lösung beiträgt, der TE schon auf den richtigen Weg gebracht wurde und das eher verwirrend gewesen sein muss und schlussendlich de fakto schlicht falsch ist.

Aber ich habe nicht vor, das hier weiter zu vertiefen. Dem TE wurde weiter geholfen hoffe ich mal und ich will den Thread nicht mit Off Topic Dingen aufblähen falls es vom TE weitere Nachfragen geben sollte.
 
Zrebna

Zrebna

Vielen Dank speziell an MoxxiManagarm, aber auch für alle anderen Antworten:)

@handshake45:
Ah, du hast ja doch ganz gut verstanden, worum es mir ging (trotz dem nicht so optimalem Threadtitel).
Deine zweite Antwort hat mir jetzt in Verbindung mit den anderen hilfreichen Antworten in diesem Thread, sowie meinem IDE-Debugger,
auch sehr weitergeholfen.
Speziell der Satz "und das geht nicht, ohne alle Methoden in umgekehrter Reihenfolge zu verlassen."
Das ist genau das, was ich auch im Debugger schön sehen konnte und macht jetzt auch ganz klar Sinn.
Nun ist klar, dass der Weg aus der Rekursion nur natürlich geht, indem man alle Methode in invertierer Reihenfolge wieder verlässt und eben hier
ganz wichtig das returned, was man returnen will.

Danke noch einmal an Alle - der Thread hat mir wirklich sehr weitergeholfen. :)
 
Thema: 

Wie kann man endgültig aus einer Rekursion ausbrechen?

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben