Wie kann man endgültig aus einer Rekursion ausbrechen?

Zrebna

Bekanntes 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

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

Bekanntes 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?
 

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.
 
K

kneitzel

Gast
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

Bekanntes 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

Bekanntes 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

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;
    }
 

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.
 
K

kneitzel

Gast
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

Bekanntes 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
O Text aus einer Textdatei rausholen, der zwischen zwei Schlüsselworten steht Allgemeine Java-Themen 4
V Umgang mit fehlenden Daten in einer Java-Datenanalyseanwendung Allgemeine Java-Themen 5
M Methodenübersicht einer Klasse einsehen Allgemeine Java-Themen 14
T JNA, Aufruf der Funktionen einer dll Allgemeine Java-Themen 5
I Vom Monolith zu Services in einer Webseite Allgemeine Java-Themen 1
W Variable Initialisierung mit dem Ergebnis einer Regex Allgemeine Java-Themen 1
O Werte einer Generic LinkedList zusammenrechenen Allgemeine Java-Themen 14
C Sortieren und Selektieren einer ArrayList<Point3D> Allgemeine Java-Themen 6
A Einzelne Objekte und Unterobjekte einer ArrayList ausgeben Allgemeine Java-Themen 53
TheSepp Wie kann man Leerzeichen aus einer Array liste entfernen? Allgemeine Java-Themen 10
B Ein Objekt einer Klasse mehreren anderen Klassen zur Verfügung stellen? Allgemeine Java-Themen 6
M Optimierung einer Methode (byte-Geraffel) Allgemeine Java-Themen 2
I Wie kann ich den Wert aus einer If abfrage ausgeben Allgemeine Java-Themen 23
S HTML einer Webseite 1:1 so bekommen wie es auch der Browser anzeigt? Allgemeine Java-Themen 14
melaniemueller Einzelne Zeile aus einer txt Datei in einem String speichern Allgemeine Java-Themen 12
L Java überprüfen lassen, ob sich ein gegebener Pfad / das Programm an sich auf einer CD oder Festplatte befindet Allgemeine Java-Themen 14
J (Geplante) Änderungen an einer Datei vorübergehend speichern und anwenden? Allgemeine Java-Themen 12
ME2002 Fragen aus einer Java Klausur Allgemeine Java-Themen 67
_user_q Obfuscate einer .jar-Datei mit ProGuard? Allgemeine Java-Themen 2
_user_q Verknüpfung einer .jar-Datei (liegt z. B. auf dem Desktop) im Autostart-Ordner erstellen? Allgemeine Java-Themen 20
C Parsen einer sich updatenden Html mithilfe von jsoup Allgemeine Java-Themen 4
E Eine Methode einer extendeten Klasse deakitivieren Allgemeine Java-Themen 12
H Performance einer Monte-Carlo-Simulation verbessern Allgemeine Java-Themen 6
LimDul Kam eine java.net.URL zu einer HashMap und ging als DNS Anfrage wieder heraus Allgemeine Java-Themen 18
E Variablen Nach Übergabe einer Variable den Constructor aufrufen Allgemeine Java-Themen 16
Zeppi NullPointerException in einer if-Abfrage Allgemeine Java-Themen 6
D Abbruch einer ViewScoped Bean in Arbeit Allgemeine Java-Themen 2
Lukas2904 Schleife mit ansteuerung einer Klasse Allgemeine Java-Themen 5
d.lumpi Aus Einer Klasse auf ein Objekt einer anderen Klasse Zugreifen Allgemeine Java-Themen 1
Lukas2904 Wie kann man cps (ClicksPerSecond) in einer GUI anzeigen lassen? Allgemeine Java-Themen 4
O Produziert das Tool "jpackage" (ab JDK 14) .exe Dateien, die auf einer Zielumgebung ohne JRE lauffähig sind ?` Allgemeine Java-Themen 7
R Lambda Expression in einer Methode execute() aufrufen (execute() ist eine Methode aus dem funktionalen Interface Command) Allgemeine Java-Themen 5
Drachenbauer wie kann ich alle instanzen einer Klasse durchsehen, ohne, dass diese in einer Liste erzeugt wurden? Allgemeine Java-Themen 11
N BlueJ Implementation einer Analoguhr Allgemeine Java-Themen 0
O Formatierte String ausgabe bei vier Variablen in einer Zeile Allgemeine Java-Themen 1
N Speicherort einer Datei im Explorer ändern Allgemeine Java-Themen 8
O Datentypen Wie kann ich den Typ einer ArrayList abfragen ? Allgemeine Java-Themen 7
O Leerzeichen und Umlaute im Pfad einer Java Applikation machen Probleme Allgemeine Java-Themen 13
H Mehrere PNG-Files in einer Datei Allgemeine Java-Themen 9
G Java Editor Löschen doppelter Zahlen einer Liste Allgemeine Java-Themen 2
J JSON Daten von einer Webseite erhalten Allgemeine Java-Themen 2
L RegEx für Teile einer Berechnung Allgemeine Java-Themen 14
L Erste Schritte TDD testen einer Methode mit injezierten Services? Allgemeine Java-Themen 12
J Zerlegen einer Zahl Allgemeine Java-Themen 6
MiMa 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
MiMa Prüfziffer einer EAN Nummer berechnen Allgemeine Java-Themen 4
MiMa 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
temi 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
ReinerCoder 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

Ähnliche Java Themen

Neue Themen


Oben