# Rekursiv definierte Methoden!



## mausi_1986 (29. Dez 2009)

Hallo!

Ich sitze grade an folgender Aufgabe:

Gegeben sei die folgende rekursiv definierte Methode f:


```
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(7,8)? In welcher Reihenfolge und mit welchen Parametern
wird f dabei rekursiv aufgerufen? Geben Sie die Reihenfolge der Aufrufe explizit
an.

Die Lsg. dazu habe ich auch, aber ich verstehe das nicht so ganz, hier die Lsg.:

Lösung:
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)

f( 7, 8) = -3

Anzahl der Aufrufe: 11

Kann mir mal bitte ejemand erklären wie ich vom 1. Aufruf zum 2. Aufruf komme?
Ich hätte für den 2. Aufruf : f(3,-5) geschrieben, und wie komme ich zum schluss auf f(7,8) = -3? Bzw. wann weiss ich wann ich aufhören muss...

Bin für jede Hilfe dankbar

lg mausi_1986


----------



## eRaaaa (29. Dez 2009)

mausi_1986 hat gesagt.:


> Ich hätte für den 2. Aufruf : f(3,-5) geschrieben



naja, x= 7 ... 7-3 = 4 (wie kommst du da auf 3 ? ) und y= 8 .. 8/3 = 2 (da int/int = int)

also ergibt sich f(4,2) -  *hier der 3. Aufruf* f( 5, 9)



> Bzw. wann weiss ich wann ich aufhören muss...



Nunja, wenn irgendwann alle f`s halt in keinen weiteren rekursiven Aufruf, also wenn x < 1 oder y <=2 endet


----------



## Mausi_1986 (29. Dez 2009)

also muss ich f(x - 3, y / 3) nehmen?

so dass ich auf f (7-3,8/3) = f(4,2) komme?

und was ist dann mit dem rest in der zeile? also


```
return 2 * f(x - 3, y / 3) - f(x - 2, y + 1);
```

aber dann verstehe ich nihct wie ich beim 3. aufruf auf f(5,9) kommen soll...da wäre doch y dann <=2 und somit müsste doch -2 zurückgegeben werden und nicht 9 oder bin ich jetzt blöde...


----------



## eRaaaa (29. Dez 2009)

Mausi_1986 hat gesagt.:


> aber dann verstehe ich nihct wie ich beim 3. aufruf auf f(5,9) kommen soll...da wäre doch y dann <=2 und somit müsste doch -2 zurückgegeben werden und nicht 9 oder bin ich jetzt blöde...



Richtig, das gilt aber nur für das Ergebnis des ersten f, du hast ja aber zweimal den Aufruf der Methode :

f(4,2) - f(5,9)

Das f(5,9) muss ja trotzdem noch weiter ausgewertet werden!

2*-2-2 - 2 * f(2,3) - f(3,10)  (wenn ich mich jetzt mit den zwei`en nicht verschaut habe  )

usw. ....


----------



## Mausi_1986 (29. Dez 2009)

Also tut mir leid ich steig da nicht durch, ich versuchs mal zuerklären wie weit ich mitkomme.

1.Aufruf ist mir klar f(7,8)
2.Aufruf f(7-3,8/3) = f(4,2)
3.Aufruf f(7-2,8+1) = f(5,9)
4.Aufruf f(5-3,9/3) = f(2,3)

hätte ich den 4. aufruf auch durch f(4-2,2+1) errechnen können?


----------



## Milo (29. Dez 2009)

Hi,

Du kannst Dir das vll als eine Art Baum vorstelle. Jeder Aufruf erzeugt wiederum 2 neue Aufrufe, bis eine der beiden Bedingungen erfüllt ist. Dein Aufruf 2 und 3 passieren also auf der gleichen Ebene.

1. Aufruf f(7,8)

2.1 Aufruf f(7-3,8/3) = f(4,2) --> Ende, da y == 2
2.2 Aufruf f(7-2,8+1) = f(5,9)

3.1 und 3.2 gibts nicht mehr
3.3 Aufruf f(5-3,9/3) = f(2,3)
3.4 Aufruf f(5-2,9+1) = f(3,10)

4.1, 4.2, 4.3 und 4.4 existieren nicht mehr
4.5 Aufruf f(2-3,3/3) = f(-1,1) --> Ende, da x < 1
4.6 Aufruf f(2-2,3+1) = f(0,4) --> Ende, da x < 1
4.7 Aufruf f(3-3,10/3) = f(0,3) --> Ende, da x < 1
4.8 Aufruf f(3-2,10+1) = f(1,11) 

5.1, 5.2, 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 5.9, 5.10, 5.11, 5.12, 5.13, 5.14 gibts nicht mehr
5.15 Aufruf f(1-3,11/3) = f(-2,3) --> Ende, da x < 1
5.16 Aufruf f(1-2,11+1) = f(-1,12) --> Ende, da x < 1

Gruß Micha


----------



## Mausi_1986 (29. Dez 2009)

Ahhh!

Vielen dank jetzt verstehe ich das...vielen vielen Dank Milo! und dir auch eRaaaa...dann setz ich mich jetzt mal an die nächsten aufgaben 

danke nochmals

lg


mausi!


----------



## Mausi_1986 (29. Dez 2009)

So, die nächste aufgabe, ging mir sehr leicht von der hand, dank der lsg konnte ich alles als richtig verzeichnen 


eine frage hätte ich allerdings noch wie komme ich auf f( 7, 8) = -3 im oben genannten beispiel?

lg

mausi


----------



## Milo (30. Dez 2009)

Hi,

nun musst Du immer schauen, wann die Methode einen "echten" Rückgabewert hatte und sich nicht selbst aufgerufen hat. Ich bin kein Informatiker. Ich würde nun einfach von hinten durchgehen und schauen, welche Teillösung zu welchem Zweig gehört.

Aus 5.15 und 5.16 ergibt sich 4.8 --> -1 = (2*(-1) - (-1))
Aus 4.7 und 4.8 ergibt sich 3.4 --> -1
Aus 4.5 und 4.6 ergibt sich 3.3 --> -1
Aus 3.3 und 3.4 ergibt sich 2.2 --> -1
Aus 2.1 und 2.2 ergibt sich 1  --> -3

Gruß Micha


----------

