Rekursionsaufgabe lösen

Bitte aktiviere JavaScript!
Moin, ich würde gerne die Aufgabe im Anhang als Übung lösen. Wie geht man da am schnellsten und sichersten vor? Es handelt sich um eine Klausuraufgabe.

Für den ersten Aufruf f(16,3) würde er, sofern ich nichts falsch gemacht habe

2+f{f(13,3), 3/2] zurückgeben. Wenn das richtig ist wie würde der Aufrufbaum bei soetwas aussehen (sofern ein Aufrufbaum die eleganteste Vorgehensweise ist das zu lösen).

Kann mir jemand ein Ratschlag geben? Im Internet finde ich nur sehr einfache Beispiele die mir gar nicht helfen...

lg
 

Anhänge

Ist diese Vorgehensweise allgemein für Rekursionen empfehlbar? Finde das doch etwas übersichtlicher als Aufrufbäume ...

 
Man nimmt sich Papier und Bleistift und geht die Methode durch. Am Ende landest du, wie du schon geschrieben hast bei 2+f{f(13,3), 3/2], dann führst du die funktion mit den neuen Parametern neu auf, also 13 und 3, da kommt das Ergebnis x raus, dann führst du sie mit x, 3/2 aus

Ich habe mir das Video KURZ angeschaut, es bietet eine gute Lösung, passt aber nicht zur Aufgabe
 
Wie geht man da am schnellsten und sichersten vor?
So wie es @L0oNY geschrieben hat: einfach durchgehen.

Die rekursiven Aufrufe finden an der Stelle 2+f(f(x-3, y), y/2) statt. Die Rekursion endet, falls x == 1 oder y <= 1 gilt. Damit lässt sich die letzte Frage sofort beantworten: da beim Aufruf von f(x-3, y) das y nicht verändert wird, endet die Rekursion nur dann, wenn x irgendwann genau x == 1 endet, wird die Rekursion f(x-3,y) endlos ausgeführt, wenn y > 1 gilt und x-1 kein Vielfaches von 3 ist.

Code:
1: f(16,3) = 2+f(f(13,3),1)
2: f(13,3) = 2+f(f(10,3),1)
3: f(10,3) = 2+f(f(7,3),1)
4: f(7,3) = 2+f(f(4,3),1)
5: f(4,3) = 2+f(f(1,3),1)
6: f(1,3) = 2 (wg. x == 1)

5: -> f(4,3) = 2+f(f(1,3),1) = 2+f(2,1)
6: f(2,1) = 3 (wg. y == 1)
5: -> f(4,3) = 2+f(2,1) = 5

4: -> f(7,3) = 2+f(f(4,3),1) = 2+f(5,1)
5: f(5,1) = 3 (wg. y == 1)
4: -> f(7,3) = 2+f(5,1) = 5

3: -> f(10,3) = 2+f(f(7,3),1) = 2+f(5,1)
4: f(5,1) = 3 (wg. y == 1)
3: -> f(10,3) = 2+f(5,1) = 5

2: -> f(13,3) = 2+f(f(10,3),1) = 2+f(5,1)
3: f(5,1) = 3 (wg. y == 1)
2: -> f(13,3) = 2+f(5,1) = 5

1: -> f(16,3) = 2+f(f(13,3),1) = 2+f(5,1)
2: f(5,1) = 3 (wg. y == 1)
1: -> f(16,3) = 2+f(5,1) = 5
Das Ergebnis für f(16,3) ist also 5.

Die Zeilen mit "->" sind nur gedankliche Stützen, lässt man diese weg, erhält man die Reihenfolge inkl. der Parameter der Aufrufe.

Die Rekursionstiefe ist die Zahl vor dem Doppelpunkt; maximal also 6.
 
Du hast zwei Aufrufwerte, deswegen böte sich eine Wertetabelle an. Du überlegst Dir eine Darstellung vor jedem return. Du gehst es sie für f(16, 3) durch, ermittelst die Reihenfolge und Rekursiontiefe. Durch die Wertetabelle kannst du feststellen, ob sie immer ein int-Wert liefert.
Insgesamt betrachtet ist diese Aufgabe mehr als machbar...

@mihe7 Rechne ihm doch nicht alles vor...
 
Zuletzt bearbeitet:
Weiterhin kann man den gegebenen Code 1:1 in Java nachprogrammieren. Ohne explizite Ausgabe der Einzelschritte kommt "5" heraus. Interessanter wird es z.B. beim Variieren von y von 3 auf 5: dann gibt es eine StackOverflow Exception (könnte in einer Klausur auch abgefragt werden)
 
Passende Stellenanzeigen aus deiner Region:

Oben