Rekursiver Algorithmus

[juliuspilatus]

Kann mir bitte jemand sagen, wie man auf diesen rekursiven Algorithmus kommt? Also ist das ein bekannter Algorithmus? Ich habe absolut keine Ahnung, wie man z.B. bei f(3) auf das Ergebnis 6 kommt und wie dieser Algorithmus überhaupt im Allgemeinen funktioniert




Vielen Dank im voraus

 

[KonradN]

Der Algorithmus ist doch gegeben - dann kannst Du den doch durchspielen:

Was passiert bei f(3)?
if (n % 2 == 0) --> 3%2 ist 1 - also else Zweig:
g(n) -> g(3)

Das siehst Du im Baum. f(3) ruft g(3) auf.

Was passiert nun bei g(3)? Kannst Du das weiter durchspielen?

 

[juliuspilatus]

Der Algorithmus ist doch gegeben - dann kannst Du den doch durchspielen:

Was passiert bei f(3)?
if (n % 2 == 0) --> 3%2 ist 1 - also else Zweig:
g(n) -> g(3)

Das siehst Du im Baum. f(3) ruft g(3) auf.

Was passiert nun bei g(3)? Kannst Du das weiter durchspielen?

Ich weiß, was der Code bedeutet, aber ich verstehe nicht, warum dann am Ende 6 herauskommt.

3 ist eine ungerade Zahl, und größer als 0, also rechnet man im zweiten Abschnitt f (3 - 1) + f (3 - 2). Warum kommt dann da 6 heraus?

 

[KonradN]

Ich weiß, was der Code bedeutet, aber ich verstehe nicht, warum dann am Ende 6 herauskommt.

3 ist eine ungerade Zahl, und größer als 0, also rechnet man im zweiten Abschnitt f (3 - 1) + f (3 - 2). Warum kommt dann da 6 heraus?

Spiel es weiter durch - wir bauen noch den Aufrufbaum auf - Du hast das f(2) und f(1) erst einmal erfasst ... aber noch hast Du keine Ergebnisse. Die grünen Felder sind also noch leer.

Du musst das alles ganz durchlaufen um zu den Ergebnissen zu kommen.

 

[KonradN]

Ich unterstelle einfach einmal, dass Du den Aufrufbaum selbst erst einmal verstanden hast. Und damit zu den Ergebnissen kommen kannst.

Das ist hier in der Aufgabe extrem heftig, denn es wird eine globale Variable verwendet. Damit wäre bei jedem Aufruf das Ergebnis ein Anderes.

Aber wir gehen vom ersten Lauf aus. Die Variable ist 0.

--> Was passiert bei dem return global++; genau? Das exakte Verständnis ist wichtig.

Der zweite Punkt ist: Wie läuft die Ausführung durch den Baum? Wann wird welcher Knoten wie bearbeitet? Da Du diesen aufgebaut hast, sollte klar sein: die linke Seite kommt erst, dann geht es in den rechten Teilbaum. Damit ist die Reihenfolge der return global++ Aufrufe klar und die entsprechenden Ergebnisse kommen da in den Blättern zustande.

Die Knoten sind dann einfache Berechnungen - Du hast ja klare return Befehle. Damit kannst Du die Werte von den Blättern hoch in den Knoten führen. So kommst Du dann am Ende zu dem Ergebnis.

 

[juliuspilatus]

Ich unterstelle einfach einmal, dass Du den Aufrufbaum selbst erst einmal verstanden hast. Und damit zu den Ergebnissen kommen kannst.

Das ist hier in der Aufgabe extrem heftig, denn es wird eine globale Variable verwendet. Damit wäre bei jedem Aufruf das Ergebnis ein Anderes.

Aber wir gehen vom ersten Lauf aus. Die Variable ist 0.

--> Was passiert bei dem return global++; genau? Das exakte Verständnis ist wichtig.

Der zweite Punkt ist: Wie läuft die Ausführung durch den Baum? Wann wird welcher Knoten wie bearbeitet? Da Du diesen aufgebaut hast, sollte klar sein: die linke Seite kommt erst, dann geht es in den rechten Teilbaum. Damit ist die Reihenfolge der return global++ Aufrufe klar und die entsprechenden Ergebnisse kommen da in den Blättern zustande.

Die Knoten sind dann einfache Berechnungen - Du hast ja klare return Befehle. Damit kannst Du die Werte von den Blättern hoch in den Knoten führen. So kommst Du dann am Ende zu dem Ergebnis.

Den Aufbau habe ich nun verstanden. Das global ++ soll bedeuten, dass die global Variable um 1 erhöht wird. Aber ich verstehe irgendwie immer noch nicht, wie man auf die Ergebnisse kommt. Warum f(3) = 6 oder f (2) links = 1 und f(1) rechts = 5. Wie wird das berechnet?

 

[juliuspilatus]

Ok also die Werte links und rechts werden dann einfach addiert und die global variable bedeutet, dass der Baum endet, wenn diese auf 1 gesetzt wird, verstehe ich das richtig?

 

[KonradN]

Die globale Variable ist einfach nur ein Zähler. Immer, wenn die Methode g in den else Zweig geht, wird der aktuelle Inhalt von global zurück gegeben und danach global um eins erhöht. Du kannst zum Verständnis ja einfachmal folgenden Code betrachten und überlegen, was da ausgegeben wird - und dann das einfach ausprobieren um zu sehen, ob Du es richtig verstanden hast:

int global = 0;
System.out.println(global++);
System.out.println(global++);
System.out.println(global++);
System.out.println(global++);
System.out.println(global++);

Und dieser else Zweig wird ausgeführt in den Blättern. Und der Baum wird abgearbeitet:

• erst Teilbäume von links nach rechts
• dann den Knoten

Damit können wir diese global++ Werte in den Blättern eintragen als Rückgabe: Der erste Knoten hat daher die 0, der nächste die 1, dann die 2, ....

Und nun kannst Du die Knoten selbst behandeln. Bei f Knoten ist dies einfach - da wird ja einfach das Ergebnis vom g Knoten genommen (es findet sich ja ein return g(...); in beiden Teilen der f Methode.

Bei g haben wir im anderen if Zweig die Summe der beiden Aufrufe stehen. Da müssen wir also die Summe bilden.

 

[juliuspilatus]

Hm, keine Ahnung irgendwie verstehe ich es immer noch nicht. Die global variable wird doch kaum benutzt, da die Funktion kaum in den else Zweig geht. Sie kommt doch davor immer in return f(n-2) + f(n-1)

 

[KonradN]

Dann schau Dir noch einmal die Baumstruktur an und schau, in welchen Teilen die globale Variable verwendet wird. Das sollte Dir deutlich werden, wenn Du den Baum selbst aufbaust. Du kannst ja den Baum um paar Informationen erweitern:
- Du kannst die Zeile dazu schreiben. Beim Kopf f(3) ist dann ja 3%2 = 1 und dann das g(n) wichtig. So kommt dann ja der Child-Knoten g(3) zu stande. Was passiert da weiter?

Wenn Du einen erweiterten Baum hast, dann erkennst Du evtl. die Aufrufe.