Rekursionsaufgabe lösen

Tricky

Mitglied
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

  • rekursion.png
    rekursion.png
    31,8 KB · Aufrufe: 62

L0oNY

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

mihe7

Top Contributor
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.
 
X

Xyz1

Gast
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 von einem Moderator:

M.L.

Top Contributor
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)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
I Rekursionsaufgabe Java Basics - Anfänger-Themen 3
G Rekursionsaufgabe mit Streams Java Basics - Anfänger-Themen 5
G Code für Rekursionsaufgabe Java Basics - Anfänger-Themen 3
Alen123 Wie würdet ihr diese Aufgabenstellung lösen? Java Basics - Anfänger-Themen 18
S GUI-Programmierung Sudoku-Rätsel lösen Java Basics - Anfänger-Themen 1
L Symbo Rätsel lösen lassen Java Basics - Anfänger-Themen 3
J Array eintrag mit möglichst wenig code lösen Java Basics - Anfänger-Themen 16
D Erste Schritte Lösen dieser Aufgabe, Hilfe! Java Basics - Anfänger-Themen 12
F Switch Case Problem mit Regex lösen? Java Basics - Anfänger-Themen 6
B Türme von Hanoi mit einer beliebigen aber gültigen Eingabe lösen Java Basics - Anfänger-Themen 5
N Denksportaufgabe durch Algorithmus lösen Java Basics - Anfänger-Themen 2
K Compiler-Fehler NullPointerException lösen Java Basics - Anfänger-Themen 16
B Wie könnte man mit Java diese Matheaufgabe lösen Java Basics - Anfänger-Themen 7
kilopack15 Sin(x) rekursiv lösen Java Basics - Anfänger-Themen 17
S Lineare Gleichung lösen Java Basics - Anfänger-Themen 1
A instanceof-if-else-Anweisungen eleganter lösen Java Basics - Anfänger-Themen 5
N Von Kopf bis Fuss TestArrays lässt sich nicht lösen Java Basics - Anfänger-Themen 5
L NullPointerException lösen Java Basics - Anfänger-Themen 6
R Hanoi rekursiv lösen Problem Java Basics - Anfänger-Themen 1
A Sudoku mit Backtracking lösen Java Basics - Anfänger-Themen 3
C Gleichung mit Potenz mit einer Unbekannten lösen Java Basics - Anfänger-Themen 5
D Sudoku lösen mit Backtracking Java Basics - Anfänger-Themen 20
B Quadratische Gleichung mit JAVA lösen Java Basics - Anfänger-Themen 5
S Bisschen hilfe beim Sudoku Lösen benötigt Java Basics - Anfänger-Themen 7
I Fragen bzw. Aufgabe lösen Java Basics - Anfänger-Themen 4
C Differenz-Methode mit Array lösen Java Basics - Anfänger-Themen 14
M Sudoku Rekursiv lösen Java Basics - Anfänger-Themen 9
M Gibt es eine einfachere Variante diese Aufgabenstellung zu lösen? Java Basics - Anfänger-Themen 11
O Wie kann man das einfach lösen? (dynamisch viele Attribute) Java Basics - Anfänger-Themen 6
G methode lösen Java Basics - Anfänger-Themen 5
G Sudoku rekursiv lösen Java Basics - Anfänger-Themen 10
I Lineare Gleichungssysteme lösen -> Problem Java Basics - Anfänger-Themen 3
G (csv)Datei lesen FindBug findet mgl. NullPointer - wie lösen Java Basics - Anfänger-Themen 3
K Lösen einer Gleichung Java Basics - Anfänger-Themen 12
V wie kann man das lösen ? Java Basics - Anfänger-Themen 3
lumo lösen von: "Type safety"? Java Basics - Anfänger-Themen 4
J Mit welchem LayoutManager Problem lösen? Java Basics - Anfänger-Themen 2
A Übungsaufgabe lösen - Problem mit true und false Java Basics - Anfänger-Themen 6
J Lösen linearer Gleichungen Java Basics - Anfänger-Themen 3
N Ist dieses Problem mit Java zu lösen? Java Basics - Anfänger-Themen 7
P wait und notify oder wie soll ich es lösen Java Basics - Anfänger-Themen 2
H [req] wer kann mir helfen die aufgabe zu lösen? Java Basics - Anfänger-Themen 2
F Kann ein Problem bei Anweisungen nicht lösen Java Basics - Anfänger-Themen 4
G Aufgabe: Kann sie nicht lösen Java Basics - Anfänger-Themen 12
G quadratische Gleichung lösen Java Basics - Anfänger-Themen 2
I gleichung lösen Java Basics - Anfänger-Themen 4
S Gleichungssystem lösen Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Neue Themen


Oben