Rekursion Aufrufbaum

[PaulDo]

Was bedeutet die 3 beim Ausdruck a(6,3) ?
Beim Ausdruck a(6) würde ich links die fünf und rechts die vier hinschreiben und die fünf in vier und drei zerlegen und so weiter. Aber wie macht man es bei diesem Ausdruck?

 

[KonradN]

Kannst Du den Kontext noch etwas beschreiben?

Das sieht ansonsten erst einmal nach einem Methodenaufruf aus. Die Methode a hat da jetzt halt 2 Parameter und der erste bekommt die 6 und der zweite die 3.

Wenn es also um Rekursion gibt, dann hast Du halt eine Rekursion mit zwei Eingaben die dann definiert sind.

Also ein einfaches Beispiel (keine Ahnung, ob es Sinn ergibt - einfach mal ausgedacht):
a(x,y) = y falls x = 1
= a(x/2, y+1) falls x gerade
= a(x+1, y+2) falls x ungerade

Bei dem a(6,3) bedeutet dass (6 ist gerade) a(6,3) = a(3,4) = a(4, 6) = a(2, 7) = a(1,8) = 8
(Also einfach die Rekursion mal für dieses Beispiel durchgespielt)

Ging es in die Richtung? Falls nicht bitte einfach mehr Details liefern.

 

[PaulDo]

Kannst Du den Kontext noch etwas beschreiben?

Das sieht ansonsten erst einmal nach einem Methodenaufruf aus. Die Methode a hat da jetzt halt 2 Parameter und der erste bekommt die 6 und der zweite die 3.

Wenn es also um Rekursion gibt, dann hast Du halt eine Rekursion mit zwei Eingaben die dann definiert sind.

Also ein einfaches Beispiel (keine Ahnung, ob es Sinn ergibt - einfach mal ausgedacht):
a(x,y) = y falls x = 1
= a(x/2, y+1) falls x gerade
= a(x+1, y+2) falls x ungerade

Bei dem a(6,3) bedeutet dass (6 ist gerade) a(6,3) = a(3,4) = a(4, 6) = a(2, 7) = a(1,8) = 8
(Also einfach die Rekursion mal für dieses Beispiel durchgespielt)

Ging es in die Richtung? Falls nicht bitte einfach mehr Details liefern.

Hier mal die Aufgabe:
int a(int x, int y) {
if (x <= 0 || y < 0) {
return x - y + 2;
}
if (x % 2 == 0) {
return a(x / 2, y) + a(x, y - 1);
}
return a(x - 1, y - 2);
}


Vervollständigen Sie nun den Aufrufbaum für a(6, 3) aus Abbildung 1 . Die Wurzel stellt dabei den Aufruf a(6,3) dar. Die Kinder eines Knoten sind die jeweils auftretenden Methodenaufrufe bei der Ausführung des Elternknotens.


Der erste Knoten links ist a(3/3) mit einem Strang weiter nach unten und rechts a(6/2) mit zwei Strangs nach unten.
Diesen Aufbau verstehe ich nicht. Wie entsteht a(3/3) und wie a(6/2)?

 

[KonradN]

Du kannst das doch durchgehen im Code. Die Methode hast Du ja. Also was passiert bei a(3,3) (Hinweis: Immer auf die richtigen Zeichen achten! a(3/3) ist was anderes als a(3,3)!):
Ist x<=0 oder y < 0? Nein
ist x%2 == 0? Nein
also wird a(3-1, 3-2) aufgerufen.

Genau so kannst Du doch jeden Aufruf weiter durchgehen, oder nicht? Woran scheitert es? Ich sehe gerade keinen Ansatzpunkt Dir zu helfen, da ich gerade nicht sehe, wo es bei dir hakt.

 

[PaulDo]

Du kannst das doch durchgehen im Code. Die Methode hast Du ja. Also was passiert bei a(3,3) (Hinweis: Immer auf die richtigen Zeichen achten! a(3/3) ist was anderes als a(3,3)!):
Ist x<=0 oder y < 0? Nein
ist x%2 == 0? Nein
also wird a(3-1, 3-2) aufgerufen.

Genau so kannst Du doch jeden Aufruf weiter durchgehen, oder nicht? Woran scheitert es? Ich sehe gerade keinen Ansatzpunkt Dir zu helfen, da ich gerade nicht sehe, wo es bei dir hakt.

Danke, nun verstehe ich den Ansatz. Aber warum läuft ist diese Funktion nicht unendlich?

 

[PaulDo]

Danke, nun verstehe ich den Ansatz. Aber warum läuft diese Funktion nicht unendlich? Wenn x oder y 0 oder kleiner 0 ist, dann wird doch immer die erste if Anweisung ausgeführt? Ich war der Auffassung, dass bei 0 oder minus eigentlich eine 1 oder 0 geworfen werden müsste und dies sind dann die Blätter?

 

[Jw456]

Wenn x oder y 0 oder kleiner 0 ist, wird keiner Rekursion mehr gemacht es wird nur das Ergebnis zurückgegen, kein Aufruf von sich selber mehr .
Das ist ja deine Abbruch Bedingung, was jede Rekursion haben sollte .

Tipp: was macht return?

​

 

[PaulDo]

Wenn x oder y 0 oder kleiner 0 ist, wird keiner Rekursion mehr gemacht es wird nur das Ergebnis zurückgegen, kein Aufruf von sich selber mehr .
Das ist ja deine Abbruch Bedingung, was jede Rekursion haben sollte .

Tipp: was macht return?

​

Danke! Return hat die Funktion von =