Rekursiv definierte Methoden!

M

mausi_1986

Gast
Hallo!

Ich sitze grade an folgender Aufgabe:

Gegeben sei die folgende rekursiv definierte Methode f:

Java:
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

Top Contributor
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
 
Zuletzt bearbeitet:
M

Mausi_1986

Gast
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

Java:
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

Top Contributor
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 :D )

usw. ....
 
Zuletzt bearbeitet:
M

Mausi_1986

Gast
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

Bekanntes Mitglied
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
 
M

Mausi_1986

Gast
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!
 
M

Mausi_1986

Gast
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

Bekanntes Mitglied
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
 

Neue Themen


Oben