Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Rekursion » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Rekursion
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
KalleKann
unregistriert
Rekursion Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 537
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Rekursion