Wie kann man endgültig aus einer Rekursion ausbrechen?

Zrebna

Zrebna

Aktives Mitglied
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

Top Contributor
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

Aktives Mitglied
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

Top Contributor
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.
 
kneitzel

kneitzel

Top Contributor
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

Aktives Mitglied
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

Aktives Mitglied
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

Top Contributor
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

Bekanntes Mitglied
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.
 
kneitzel

kneitzel

Top Contributor
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

Aktives Mitglied
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. :)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L RegEx für Teile einer Berechnung Allgemeine Java-Themen 5
L Erste Schritte TDD testen einer Methode mit injezierten Services? Allgemeine Java-Themen 12
J Zerlegen einer Zahl Allgemeine Java-Themen 6
M Person in einer Arraylist hinzugügen mit Prüfung ? Allgemeine Java-Themen 6
Meeresgott Effizientester Weg um nach der Value einer verschachtelten Map aufzulösen Allgemeine Java-Themen 5
H Mehrere Datentypen in einer Arraylist speichern Allgemeine Java-Themen 9
M Prüfziffer einer EAN Nummer berechnen Allgemeine Java-Themen 4
M Erstellungsdatum einer Datei Allgemeine Java-Themen 10
Drachenbauer Wie kann ich einer existierenden Enum von außerhalb veränderte Werte zuweisen? Allgemeine Java-Themen 5
S HTML den ich von einer URL hole nicht identisch mit dem HTML im Browser Allgemeine Java-Themen 1
S Rückgabe einer HttpURLConnection für eine Seite einlesen bei der man eingeloggt ist..? Allgemeine Java-Themen 5
O Java-Applikation tut in Netbeans, als JAR nicht, wegen Pfadangaben einer benötigten Datei Allgemeine Java-Themen 8
M Hilfe bei einer Java Programmieraufgabe! Ab morgen Montag um 08:00 Uhr Allgemeine Java-Themen 5
J Algorithmen Analyse einer Schleife Allgemeine Java-Themen 6
Drachenbauer Wie finde ich den Aufrufer zu einer Methode, die sich nicht in meinem Projekt befindet? Allgemeine Java-Themen 2
J Die Letzte Zahl aus einer Text datei lesen Allgemeine Java-Themen 8
P einen public <Optinal String> in einer anderen Klasse mit einem Int vergleichen Allgemeine Java-Themen 2
A Mithilfe von einer Nummer einen Namen finden n-Beziehung Allgemeine Java-Themen 8
Scream_ilias Auf einer Website die anmeldedaten eingeben Allgemeine Java-Themen 9
V Threads Probleme beim Aufrufen von Methoden einer anderen Klasse (Threads) Allgemeine Java-Themen 14
I Lohnt sich heutzutage der Aufwand einer Portierung für MacOS Allgemeine Java-Themen 8
J Suchen von einer Scannereingabe in einem HashSet Allgemeine Java-Themen 1
M Konstruktor einer Methode Allgemeine Java-Themen 35
L Echtzeitdaten aus einer Webseite ziehen mit Java Allgemeine Java-Themen 19
V EMail, Attachments auslesen von einer Email Allgemeine Java-Themen 0
T Google Links in einer Liste Allgemeine Java-Themen 4
T Sinn einer toString Methode Allgemeine Java-Themen 3
P Durchlaufen einer Queue Allgemeine Java-Themen 9
J Größe einer CD ermitteln Allgemeine Java-Themen 10
L Operatoren Java Reflections: Alle Methoden einer Klasse aufrufen ohne Exceptions Allgemeine Java-Themen 5
H Länge einer verketteten Liste Allgemeine Java-Themen 4
B Quellcode einer Java libary finden um zu copy & paste'n Allgemeine Java-Themen 5
N Daten einer JCoTable in JTextArea anzeigen Allgemeine Java-Themen 7
sascha-sphw Java 9 module Zugriff auf eine resource einer anderen JAR Allgemeine Java-Themen 0
N Generic Type einer Generischen Klasse während der Laufzeit bekommen Allgemeine Java-Themen 2
E Erstellen einer Liste mit einer maximalen Menge an Elementen Allgemeine Java-Themen 13
M Wie kann ich ein int[] Array in einer Methode benutzen? Allgemeine Java-Themen 6
T Compiler-Fehler NoClassDefFoundError beim Laden einer Class Allgemeine Java-Themen 11
H Klassen LibGDX - Verschiedene Klassen als Value in einer Map Allgemeine Java-Themen 8
P Element einer Liste wurde hinzugefügt, aber es gibt keinen Zugriff Allgemeine Java-Themen 2
E Elemente innerhalb einer ArrayList vergleichen Allgemeine Java-Themen 33
J Einen Thread in einer Schleife Allgemeine Java-Themen 2
T Java Programm aus einer DB laden und starten Allgemeine Java-Themen 2
J int Werte in einer anderen Klasse in Arrays speichern Allgemeine Java-Themen 3
S Hilfe bei dem Auslesen einer YAML Datei Allgemeine Java-Themen 8
D Warum kann ich eine (deflaut) Klasse aus einer Libary in einem anderen Projekt benutzen? Allgemeine Java-Themen 3
B Generelle Frage bei einer Webanwendung / Reduzierung von DB Abfragen Allgemeine Java-Themen 1
scitex Methode einer Klasse meldet Fehler "misplaced construct(s)" Allgemeine Java-Themen 13
L Fehler bei der Ausführung einer Jar Allgemeine Java-Themen 2
Javafan01 Deklarieren einer Math.random() Zufallszahl Allgemeine Java-Themen 16
A Probleme beim Verstehen einer Aufgabenstellung Allgemeine Java-Themen 11
H Laden einer (Resourcendatei) aus einem Jar-File Allgemeine Java-Themen 17
P Array einer abstrakten Klasse Allgemeine Java-Themen 4
J Teil einer URL auslesen Allgemeine Java-Themen 13
J Ordner und Datei Struktur einer War Datei Allgemeine Java-Themen 1
F Problem beim Einlesen einer Textdatei Allgemeine Java-Themen 12
J Zugriff auf erstellte Objekte einer Klasse von einer Klasse ausserhalb Allgemeine Java-Themen 3
K Gespeicherte Daten von einer LinkedList auf vier LinkedList verteilen Allgemeine Java-Themen 6
L Seite einer Partner Website neu laden Allgemeine Java-Themen 1
M Date aus einer ArrayList<Date> holen ?? Allgemeine Java-Themen 5
kodela Dynamisches Array in einer Klasse Allgemeine Java-Themen 5
M ArrayList Rückgabewerte aus einer Funktion Allgemeine Java-Themen 15
K Erste Schritte Start einer JAR Datei 2 Wege aber einmal nicht die volle Funktionlität Allgemeine Java-Themen 20
kodela Übergabe einer Referenz Allgemeine Java-Themen 20
S Anwendung die alle Abhaengigkeiten einer Library listet..? Allgemeine Java-Themen 5
L Classpath Relativer Pfad einer Resource? Allgemeine Java-Themen 9
D HTTP Aufruf einer Methode aus einem Servlet heraus Allgemeine Java-Themen 0
RalleYTN Audiolänge einer MP3 Datei erhalten ohne diese vollständig zu laden Allgemeine Java-Themen 15
K Summierung einer Variablen Allgemeine Java-Themen 5
S Code 'innerhalb' des synchronen Bereichs einer BlockingQueue ausfuehren..? Allgemeine Java-Themen 7
B Gibt es eine Funktion die den Datentyp einer Variablen ermittelt? Allgemeine Java-Themen 8
A Erste Schritte Daten aus einer Website auslesen Allgemeine Java-Themen 7
G Ant Probleme bei einer Installation die Apache ant+ivy verwendet Allgemeine Java-Themen 14
J Bei einer Zufallsausgabe werden zu viel Ergebnisse ausgegeben Allgemeine Java-Themen 16
S libGDX mehrere Texturen zu Einer zusammenfassen Allgemeine Java-Themen 0
GreenTeaYT Verstehe nicht ganz das Observer Pattern in einer Arrayliste? Allgemeine Java-Themen 3
T Drucken einer PDF Datei Allgemeine Java-Themen 4
L Methoden Automatischer login auf einer seite Allgemeine Java-Themen 3
G Umsetzen einer Formel in Java Allgemeine Java-Themen 10
FrittenFritze Swing Apache Batik - Zoom an einer bestimmten Stelle Allgemeine Java-Themen 4
FrittenFritze Problem mit einer JComboBox, Event temporär deaktivieren Allgemeine Java-Themen 11
P mehrer Verschiedene Objekte in einer Klasse erstellen. Allgemeine Java-Themen 4
Messoras Klassen Sämtliche Variablen einer Klasse übernehmen Allgemeine Java-Themen 6
T Methoden Methode zum durchsuchen einer ArrayList Allgemeine Java-Themen 8
D Returnwert aus einer Methode gerundet ausgeben lassen Allgemeine Java-Themen 2
C Ausführen einer .JAR Datei Allgemeine Java-Themen 5
B Wie vergleiche ich Strings in einer Liste? Allgemeine Java-Themen 5
B JAVA Prozesse in einer eigenen Anwendung laufen lassen Allgemeine Java-Themen 9
H OOP Testen einer Exception mit JUnit Allgemeine Java-Themen 8
N Methoden Methoden einer Klasse auf Grundlage eines Strings aufrufen Allgemeine Java-Themen 6
JG12111989 FileInputStream - Breite einer bmp-Datei?? Allgemeine Java-Themen 8
K Auf einer Website nach einem String suchen Allgemeine Java-Themen 5
I HTML einer Website auslesen liefert nur head Allgemeine Java-Themen 6
D Erste Schritte Array von einer forschleife nach ausserhalb trasferieren Allgemeine Java-Themen 3
B Hintergrundgeräusche/Störgeräusche aus einer Sounddatei herausfiltern Allgemeine Java-Themen 2
S Algorithmus um Objekte auf einer Flaeche mit gleichem Abstand anzuordnen..? Allgemeine Java-Themen 20
T Menge an Elementen aus einer LinkedList Allgemeine Java-Themen 6
A Collections Inhalt einer Liste mit Inhalt anderer Liste vergleichen ? Allgemeine Java-Themen 7
K Input/Output String aus einer Datei einlesen und in anderer Datei speichern Allgemeine Java-Themen 20
Z NullPointerException beim Schreiben einer ArrayList in eine Datei Allgemeine Java-Themen 6

Ähnliche Java Themen

Anzeige

Neue Themen


Oben