[Progra] Rekursion

[dvs]

Hi,
hat jemand ein Paar Tips, wie man vorgehen sollte um auf etwas kompliziertere, rekursive Lösungen in Java zu kommen?
Ich finde es schwer, sich vorzustellen, wie man z.B. aus einem Binärbaum nach einem bestimmten Muster eine Liste mit Knotenwerten konstruirt.

[user]

Also für Rekursion gibts halt das reguläre Grundkonzept:

1. Basisfälle isolieren und implementieren,
2. Andere fälle rekursiv zerlegen.

Im allgemeinen solltest du vermutlich einfach so lange irgendwelche Beispiele durcharbeiten, bis du das einfach kannst. Rekursion ist ein so grundlegendes Konzept, das muss man halt irgendwo einfach verstehen. Genau wie z.B. vollständige Induktion.

[cracki]

du hast ne datenstruktur. sei das mal ein baum in seiner gaenze.

du willst ne funktion zum plaetten schreiben. die funktion nimmt dann natuerlich das wurzelelement, weil von dem aus der ganze baum erreichbar ist.

da der baum ganz uniform aus knoten aufgebaut ist, ist jeder knoten im baum ein "wurzelelement" seines unterbaumes.

was kann man mit nem knoten alles anfangen? er hat nen wert und die beiden unterbaeume.

wenn ich den baum plaetten will, reicht es, die plaettung des linken unterbaumes, den wert des wurzelelementes, und die plaettung des rechten unterbaumes aneinanderzuhaengen.

sprich (jetzt mal haskell, ist kuerzer)

Code: Alles auswählen

data Baum a = Knoten Baum a Baum | Nix

plaetten Nix = []
plaetten (Knoten l v r) = (plaetten l) ++ [v] ++ (plaetten r)

und fertig.

was passiert?

in jedem rekursionsschritt wird das grosse problem in kleinere probleme zerlegt und die teilloesungen in einem einfachen schritt kombiniert.

weil die teilprobleme immer kleiner werden, kommt irgendwann ein basisfall raus, der ebenfalls eine einfache loesung hat (in dem fall, wenn ein blatt vorliegt, also "Nix").


anderes problem: die listenverkettung kann ziemlich ineffizient sein (quiz: warum?). in java wuerde ich dann z.b. erstmal alle elemente des baumes zaehlen wollen, um die laenge der fertigen liste zu ermitteln.

Code: Alles auswählen

gewicht Nix = 0
gewicht (Knoten l v r) = (gewicht l) + 1 + (gewicht r)

int[] plaetten(Knoten w) {
    int anzahl = gewicht(w);
    int[] res = new int[w];
    wirklich_plaetten(res, 0, w);
}

int wirklich_plaetten(int[] ergebnis, int position, Knoten w) {
    if (w == null)
        return position;

    position = wirklich_plaetten(ergebnis, position, w.links);
    ergebnis[position] = w.wert;
    position = wirklich_plaetten(ergebnis, position+1, w.rechts);
    return position;
}

wirklich_plaetten fuegt dabei die werte des baumes ab der stelle "position" ins array "ergebnis" ein und gibt die stelle zurueck, ab der im "ergebnis" noch platz ist.

[dvs]

wird beim ausführen von

plaetten (Knoten l v r) = (plaetten l) ++ [v] ++ (plaetten r)

zuerst plaetten l bis zum "Nix" ausgeführt und erst danach plaetten r oder werden plaetten l und plaetten r parallel ausgewertet ?

in Java z.B. bei AnzahlBlatter im Binärbaum wird mit return 1+count(a.links)+count(a.rechts) auch parallel ausgewertet oder zuertst count(a.links) ??

[C-Otto]

In Java wird von links nach rechts ausgewertet, das heisst "plaetten l" (wenn man das so schreiben will...) wird so lange rekursiv ausgewertet, bis man beim Basisfall ist. Erst dann wird die Rekursion abgewickelt und es wird mit dem mittleren Element bzw. rechten Zweig weitergemacht. Die Auswertungsstrategie von Haskell ist hier etwas wilder, hier wird nur so weit ausgewertet, wie es gefordert ist. Eine Funktion, die nur daran interessiert ist, ob die uebergebene Liste nicht leer ist, wertet ihr Argument entsprechend wenig aus.

Ciao,
Carsten

[dvs]

ok, und wenn ich sowas habe:

current . links = loescheBlaetter ( current . links , wert ) ;

auf welches current.links zeigt current.links links vom Gleichheitzeichen ?
Sind es verschiedene current. links links und in den Klammern?
Sowas zerreißt mir das Gehirn, Hilfe ! ))

[mugen]

ok, und wenn ich sowas habe:

current . links = loescheBlaetter ( current . links , wert ) ;

auf welches current.links zeigt current.links links vom Gleichheitzeichen ?
Sind es verschiedene current. links links und in den Klammern?
Sowas zerreißt mir das Gehirn, Hilfe ! ))

current.links ist current.links, es kann ja nicht verschieden definiert sein in einer Programmzeile. Durch die Funktion bekommt current.links evtl andere Werte, es ist aber immer noch der selbe Knoten!

current.links ist keine methode! ich glaube das war das was dich verwirrte? current ist ein Knoten vom Typ XYDatenstruktur und current.links einfach nur die referenz auf einen anderen Knoten vom selben Typ, dadurch entsteht die verkettung.

current = current.links; //so setzt du current auf das "linke" element(vom vorigen current aus gesehen) deiner datenstruktur

[dvs]

wird der Wert in current . links = .... erst am Ende der Rekursion eingesetzt?

[Coolcat]

wird der Wert in current . links = .... erst am Ende der Rekursion eingesetzt?

Der Wert von current.links wird zugewiesen, wenn du von dem Aufruf der Methode loescheBlaetter zurückkommst. Meinst du das?

[dvs]

ja, und welcher Knoten im Baum ist dann mit current gemeint ?


private s tat i c Knoten loescheBlaetter ( Knoten current , Vergleichbar wert )f
15 i f ( current == nul l )
16 return nul l ;
17 el se f
18 i f ( current . links == nul l && current . rechts == nul l )
19 return current . wert . gleich ( wert ) ? nul l : current ;
20 el se f
21 current . links = loescheBlaetter ( current . links , wert ) ;
22 current . rechts = loescheBlaetter ( current . rechts , wert ) ;
23 return current ;
24 g
25 g
26 g
27
28 public void loescheBlaetter ( Vergleichbar wert )f
29 thi s . wurzel = loescheBlaetter ( thi s . wurzel , wert ) ;

[ClubsieLord]

wird der Wert in current . links = .... erst am Ende der Rekursion eingesetzt?

current.links wird gesetzt, nachdem die Prozedur loescheBlaetter fertig ist. Wenn loescheBlätter rekursiv ist, dann erst nach der Rekursion.

Bin gerad nich sicher, ob das deine Frage beantwortet. Aber dir ist schon klar, dass so ein Programm sequenziell abläuft, oder? (Mal abgesehen von Multithreading.) Also eins nach dem anderen.

EDIT: Ups, da war jemand schneller. Also wenn ich das jetzt auf die Schnelle richtig geblickt hab, dann durchforstet deine Rekursion den Baum, bis es das Element gefunden hat, dessen Wert dem übergebenen Wert gleicht, und der Teilbaum darunter wird dann entfernt. current ist der Parameter deiner Funktion loescheBlaetter. Das ist nicht immer derselbe Knoten. Immer, wenn du die Funktion aufrufst, übergibst du ja einen Wert für current. Am besten malst du dir mal nen kleinen Baum auf und gehst das Programm einfach mal Schritt für Schritt durch. Is nich so einfach zu erklären. Keine Ahnung, ob dir das jetzt weiterhilft.

[dvs]

vielleicht kann jemand einen lauf für den binärbaum mit Wurzel = 3,
Blatt = 4, Blatt = 5 und Wert 4 genau vorführen?

[ClubsieLord]

vielleicht kann jemand einen lauf für den binärbaum mit Wurzel = 3,
Blatt = 4, Blatt = 5 und Wert 4 genau vorführen?

Okay, dann mal los: Linkes Blatt ist die 4 und rechtes die 5.

Also die obere Variante von löscheBlätter wird mit der Wurzel aufgerufen. current referenziert jetzt also die Wurzel. Die ist nicht null und ihre beiden Kinder auch nicht, also wird der else-Block ausgeführt. Also wird zuerst löscheBlätter mit current.links aufgerufen. So, wir haben gesagt, dass current auf die Wurzel zeigt. Also zeigt current.links auf das linke Kind der Wurzel. Jetzt wird ja die Funktion löscheBlätter noch mal aufgerufen und da zeigt jetzt current auf das linke Kind der Wurzel (weil wir es ja gerad so übergeben haben). Dies ist jetzt aber ein Blatt, also wird geguckt, ob der Wert gleich dem gegebenen ist, was auch der Fall ist. Also wird null zurückgegeben. Jetzt sind wir wieder in Zeile 21 vom vorherigen löscheBlätter-Aufruf. Dort wird jetzt current.links auf null gesetzt, denn das ist ja der Wert, den wir eben zurückgegeben haben. Die Wurzel verliert also ihr linkes Kind. Dann gehts mit dem rechten genauso weiter, nur dass dort nicht null zurückgegeben wird, weil die Werte ungleich sind; die Wurzel darf also ihr rechtes Kind behalten.

Alles verstanden? (Ich hoffe, da is jetzt kein Fehler drin, sonst biste gleich total verwirrt.)

[dvs]

ja, danke ..aber ist schon nicht so leicht, zumindest für mich.

[dvs]

noch kleine Nachfrage: Was passiert wenn keine von beiden IF-Bedingungen stimmt, dann wird ja sozusagen "nichts" an current.links zugewiesen?