Rekursiv definierte Methoden!

[mausi_1986]

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]

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]

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]

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]

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]

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]

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]

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]

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