# Rekursive Methoden



## tmove (28. Aug 2009)

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 (28. Aug 2009)

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 (28. Aug 2009)

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


----------



## tmove (28. Aug 2009)

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 (28. Aug 2009)

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 (28. Aug 2009)

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


----------



## SlaterB (28. Aug 2009)

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 (29. Aug 2009)

Habe es hinbekommen! Dankeschön


----------

