Rekursive Methoden

[tmove]

Hi! Ich habe eine Aufgabe über rekursive Methoden.

static int f(int x, int y){
if (x < 1)
return -1;
else if (y <= 2)
return -2;
else
return 2 * f(x - 3, y / 3) - f(x - 2, y + 1);
}

Welchen Wert liefert ein Aufruf von f(6,4)?
In welcher Reihenfolge und mit weclehm Parametern wird f dabei rekursiv aufgerufen?

Lsg:
Ich setzte also x = 6 und y = 4.Daraus folgt, dass bei der If-Schleife das 2. else nehmen muss. Dann setze ich x und y ein und bekomme:

2 * f(6 - 3, 4 / 3) - f(6 - 2, 4 + 1)

2 *f (3 , 4/3) - f (4 ,5 )

Was muss ich jetzt machen? Wie bekomme ich den "Wert" von f (6,4) bzw. was ist hier unter Wert zu verstehen?

Welche Reihenfolge hier aufgerufen wir weiß ich leider auch nicht.

Ich hoff ihr könnt mir helfen

 

[SlaterB]

es wird erst der linke Wert näher berechnet, also f (3 , 4/3) rekursiv aufgerufen,
das führt zu neuen Teilberechnungen usw.,

irgendwann kommen echte Zahlen raus, dann bekommst du auch ein richtiges Endergebnis


if-schleife.de

 

[Landei]

Und dran denken, dass das / bei Ganzzahlen auch für eine Ganzzahldivision steht, also 4/3 == 1 usw.

 

[tmove]

Ja danke.
Ich hab jetzt auch die Lösung für die Aufgabe gefunden. Leider werde ich daraus noch nicht ganz schlau.

f(7,8) = -3 Wieso ist das so?

1. Aufruf: f( 7, 8)
2. Aufruf: f( 4, 2)
3. Aufruf: f( 5, 9)
4. Aufruf: f( 2, 3)
5. Aufruf: f(-1, 1)
6. Aufruf: f( 0, 4)
7. Aufruf: f( 3,10)
8. Aufruf: f( 0, 3)
9. Aufruf: f( 1,11)
10. Aufruf: f(-2, 3)
11. Aufruf: f(-1,12)

Bis zum 3. Aufruf kann ich das Ergebnis nachvollziehen. Aber wie geht es dann weiter? wie komm ich dann zB zum Aufruf 4,5,...?

 

[SlaterB]

Rekursion,
der dritte Aufruf f( 5, 9) kann nicht direkt mit -1 oder -2 beantwortet werden, sondern führt zum 4. und 5. Aufruf usw.
(edit: der 5. ist ein Teil des 4.)

 

[tmove]

Sorry, das hab ich nicht kapiert. Könntest du das ein bißchen ausführlicher beschreiben wie ich auf die Aufrufe komme?

 

[SlaterB]

f(7,8) = f( 4, 2) + f( 5, 9)

f(4,2) = -2, zu Ende,
aber
f( 5, 9) wird bei der rekursiven Berechnung zu weiteren f-Aufrufen führen

 

[tmove]

Habe es hinbekommen! Dankeschön