 Rekursion |
KalleKann
unregistriert
 |
|
Guten Abend, ich sitzte gerade vor dem Thema der Rekursionen und habe bei "erweiterten" Aufgaben noch so meine Problem.
Meine Aufgabe lautet:
static inf f(int x, int y) {
if (x==1)
return y+1;
else if ( x==y)
return f(x-2, y);
else
return f(x % 2, f(x - 2, y +1) + 2);
}
Welchen Wert liefert der Aufruf f(11, 8)? in welcher Reihenfolge und mit welchen Parametern wird f dabei aufgerufen ? Geben sie die Reihenfolge explizit an.
Laut den Lösungen ist die Reihenfolge der Aufrufe:
1. f(11,8) 2. f(9,9) 3. f(7,9) 4. f(5,10) 5. f(3,11) 6. f(1,12) 7. f(1,15) 8. f(1,18)
9. f(1,21) 10. f(1,24)
Allerdings verstehe ich nicht genau woher diese Reihenfolge kommt
Über Hilfe wäre ich wirklich Dankbar
|
|
02.03.2019 18:31 |
|
|
as_string 
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
|
|
Naja, Du musst halt stur das machen, was der Computer machen würde.
Zuerst wird die Funktion mit den Werten 11 und 8 aufgerufen.
Dann kommst Du zum ersten if, das überprüft, ob x == 1 ist, das ist es nicht, also weiter zum else if, x ist aber auch ungleich y (weil das eine 11, das andere 8 ist), also weiter zum else.
Dort wird die Funktion f wieder aufgerufen, allerdings müssen vorher erst noch alle Aufruf-Argumente evaluiert werden. Das zweite Argument bestimmt sich aber auch aus der Rückgabe der Funktion f, also muss f(x-2, y+1) ---> f(11-2, 8+1) ---> f(9, 9) zuerst aufgerufen werden.
Also gehst Du in die Funktion wieder rein, mit den Werten 9 und 9. Damit landest Du im else if(x == y) Block, also wird die Funktion f(x-2, y) --> f(9-2, 9) --> f(7, 9) aufgerufen und deren Rückgabewert zurück gegeben.
Also gehst Du mit 7, 9 in die Funktion, kommst in den else Block und musst dort erst wieder den inneren Aufruf evaluieren, also f(7-2, 9+1) --> f(5, 10).
Das geht so weiter, bis man zu der Rekursions-Abbruchbedingung x==1 zu kommen. Dazu musst Du Dir aber gemerkt haben, wie Dein letzter Aufruf der Funktion f überhaupt war, und wie Du mit dem Rückgabewert weiter umgehen musst. Dazu müsst Du das machen, was auch ein Computer machen würde, nämlich einen Aufrufstack Dir merken.
Probier mal selber ein wenig!
Gruß
Marco
|
|
|
04.03.2019 10:43 |
|
|
|
