Rekursion - Tipps zum Vorgehen

[JblueG]

Hallo,

ich habe folgendes Problem. Ich bekomme es einfach nicht hin rekursive Prüfungen zu programmieren.
Ich weiß nicht wieso, ich habe eigentlich nie Probleme in analytischen und logischen Sachen und könnte für jedes Problem eine Lösung finden, nur eben keine rekursive.
Ich war auch noch nie gezwungen sowas alleine zu durchdenken...bis jezt.
Könnt ihr mir vielleicht ein paar Tipps geben, wie ich prinzipiell vorgehen kann?
Dafür wäre ich sehr dankbar!


Noch was zum konkreten Problem. Ich habe folgende Baumstruktur
-OberElement
_____- Zelle
__________-Zelle
________________-Zelle
________________-Zelle
__________-Zelle
________________-Zelle
________________-Zelle
______________________-Zelle
______________________-Zelle
__________-Zelle

Die Klasse Zelle hat dabei ein Attribut, zB boolean gelb und jeweils eine Liste von sich selbst, in der
Objekte drin sein können oder sie kann auch leer sein.
Und ich möchte diese Baumsturktur rekursiv durchgehen und überprüfen, ob das Attribut gelb IRGENDWO einmal mit true belegt ist.

WICHTIG: Ich möchte keine Lösung, also keinen JavaCode sehen. Ich möchte nur Vorschläge/Tipps, wie ich Vorgehen kann, damit ich selbst eine Lösung finde! Und die ich mir am besten auch für die Zukunft merken kann.

 

[SlaterB]

eine Eimerkette ? Wikipedia zum Löschen eines Brandes wird gebildet, was hat jeder einzelne zu tun?

an seinen Nachfolger weiterreichen, bei dir etwas an einem Unterelement aufrufen, sind mehrere vorhanden, dann eben bei all diesen,
mehr ist erstmal gar nicht konkret zu sagen, näher zu erklären gibt es dabei auch nichts,

hilft das schon?

 

[bone2]

Also ich würde einfach über alle Zellen schleifen und dann bei jeder zelle kontrollieren, ob es unterzellen gibt. gibt es welche rufe ich wieder die selbe methode auf und schleife durch alle unterzellen. das geht rekursiv so durch. es endet wenn man man keine unterzellen mehr findet oder eventuell bedingung xy erfüllt ist (sudoku löser, man kann wieder nach oben sobald ein fehler da ist) und man kommt durch die ebenen langsam wieder nach vorne

sudoku löser ist eine gute übung

 

[buzz!dev]

Wenn deine Datenstruktur bereits ein Baum ist, wieso benutzt du dann nicht eine der Traversierungen für Graphen?

 

[JblueG]

hmm also meine aktuelle Lösung sieht so aus

public static void main(String[] args) {
		
		boolean notizVorhanden = istGelbVorhanden(oberElement);
	}

	
	private static boolean istGelbVorhanden(OberElement oberElement) {
		Zelle ersteZelle = oberElement.getZelle();
		
		boolean hatNotiz = ueberpruefeZellen(ersteZelle.getZellen());
		return hatNotiz;
	}

	private static boolean ueberpruefeZellen(List<Zelle> zellen) {
		for(Zelle zelle : zellen) {
			System.out.println(zelle.getName());
			if(zelle.isGelb()) {
				return true;
			}
			if(!(zelle.getZellen()==null || zelle.getZellen().size()==0)) {
				ueberpruefeZellen(zelle.getZellen());
			}
		}
		return false;
	}

aber sie funktioniert nicht


ich glaube ich versuche erstmal eine Methode zu schreiben die einfach nur durch alle Elemente durchgeht ohne was zu prüfen

 

[SlaterB]

in Zeile 21 gibt der Rekursionsaufruf etwas zurück, aber ob true oder false, du ignorierst den Rückgabewert

ein Logging in der Methode wäre auch immer interessant, wird die Methode öfters ausgeführt?
kommt das if je erfolgreich dran? usw.

 

[JblueG]

@SlaterB

ahja stimmt...ok das kommt gleich dran...
ich hab jetzt erstmal was was überall durchläuft einmal und von allem einmal den Namen ausgibt

	public static void main(String[] args) {
		OberElement oberElement = baueElementZusammen();
		
		boolean GelbVorhanden = istGelbVorhanden(oberElement);
	}

	
	private static boolean istGelbVorhanden(OberElement oberElement) {
		Zelle ersteZelle = oberElement.getZelle();
		
		boolean hatGelb = ueberpruefeZellen(ersteZelle.getZellen());
		return hatGelb;
	}

	private static boolean ueberpruefeZellen(List<Zelle> zellen) {
		for(Zelle zelle : zellen) {
			System.out.println(zelle.getName());
			if(!(zelle.getZellen()==null || zelle.getZellen().size()==0)) {
				ueberpruefeZellen(zelle.getZellen());
			}
		}
		return false;
	}

das funktioniert auch =))

 

[SlaterB]

> ich hab jetzt erstmal was was überall durchläuft einmal und von allem einmal den Namen ausgibt

das ist natürlich ein lobenswertes Vorgehen, hattest du ja vorher schon geschrieben,
meinen Log-Vorschlag schon vorausgeeilt, soweit kommen weniger als man denkt, deshalb immer ein Extralob wert 😉

 

[JblueG]

🙂 Thx.

also so funktionierts:

	public static void main(String[] args) {
		OberElement oberElement = baueElementZusammen();
		
		boolean notizVorhanden = istGelbVorhanden(oberElement);
	}

	
	private static boolean istGelbVorhanden(OberElement oberElement) {
		Zelle ersteZelle = oberElement.getZelle();
		
		boolean hatGelb = ueberpruefeZellen(ersteZelle.getZellen());
		return hatGelb;
	}

	private static boolean ueberpruefeZellen(List<Zelle> zellen) {
		for(Zelle zelle : zellen) {
			System.out.println(zelle.getName());
			if(zelle.isGelb()) {
				return true;
			}
			if(!(zelle.getZellen()==null || zelle.getZellen().size()==0)) {
				if(ueberpruefeZellen(zelle.getZellen())== true) {
					return true;
				}
			}
		}
		return false;
	}

Allerdings scheint mir das komplizierter zu sein als nötig, weil da 2 Abprüfungen auf true sind. Eigentlich müsste 1 reichen. Wenn jemand ein Verbesserungsvorschlag einfällt nehm ich den gerne an.

 

[bone2]

das ist schon okay so, du hast ja auch 2 sachen die du prüfst bzw 3 mögliche enden:
a) du willst zurück wenn diese zelle gelb ist
b) du willst zurück wenn eine unterzelle gelb ist
c) du musst zurück wenn der ast zu ende ist

[OT]besser:

if(ueberpruefeZellen(zelle.getZellen())) {

[/OT]

 

[IchBinBabei]

import java.util.ArrayList;
import java.util.List;

public class Zelle {
	public boolean gelb;
	public List<Zelle> zellen;
	public Zelle(boolean gelb) {
		this.gelb = gelb;
		this.zellen = new ArrayList<Zelle>();
	}
	
	public boolean istGelb() {
		if (this.gelb) {
			return true;
		}
		for (Zelle zelle : zellen) {
			if (zelle.istGelb()) {
				return true;
			}
		}
		return false;
	}

    public static void main(String[] args) {
        Zelle zelle = new Zelle(false);
        zelle.zellen.add(new Zelle(false));
        zelle.zellen.get(0).zellen.add(new Zelle(false));
        zelle.zellen.get(0).zellen.get(0).zellen.add(new Zelle(true));
        zelle.zellen.get(0).zellen.get(0).zellen.add(new Zelle(false));
        zelle.zellen.get(0).zellen.add(new Zelle(false));
        zelle.zellen.get(0).zellen.get(1).zellen.add(new Zelle(false));
        zelle.zellen.get(0).zellen.get(1).zellen.add(new Zelle(true));
        zelle.zellen.get(0).zellen.get(1).zellen.get(1).zellen.add(new Zelle(false));
        zelle.zellen.get(0).zellen.get(1).zellen.get(1).zellen.add(new Zelle(false));
        zelle.zellen.get(0).zellen.add(new Zelle(false));
        
        System.out.println(zelle.istGelb());
    }
}

 

[JblueG]

@buzz!dev

???