Dein Fortschritt:
0 / 0 Aufgaben
2
Aufgabenblock — AFB II
Zehn Aufgaben aus allen Unterkapiteln: Methoden analysieren, Ausgaben beim Ab- und Aufstieg ermitteln, Rekursion und Iteration vergleichen, Vergleichszahlen herleiten — mit gestuften Tipps, wenn du nicht weiterkommst.
A1
Eine unbekannte Methode
AFB IIstatic int m(int a, int b) {
if (b == 0) {
return a;
}
return m(b, a % b);
}Analysieren Sie den Aufruf m(84, 36): Geben Sie den Rückgabewert und die Anzahl der Aufrufe an und nennen Sie, was die Methode berechnet.
Ansatz: Verfolgen Sie die Parameter: Aus
(a, b) wird (b, a % b).Rechenweg: 84 % 36 = 12 → m(36, 12); 36 % 12 = 0 → m(12, 0) liefert 12.
Lösung: a) 12 b) 3
Vollständige Lösung
Aufrufe:
m(84, 36) → m(36, 12) → m(12, 0). Der dritte Aufruf erfüllt die Abbruchbedingung und liefert 12; der Wert wird unverändert nach oben durchgereicht. Die Methode berechnet den größten gemeinsamen Teiler nach dem euklidischen Algorithmus. Weil der Selbstaufruf die letzte Aktion ist (return m(…)), ist sie endrekursiv und lässt sich direkt als Schleife schreiben.A2
Ausgabe vor und nach dem Aufruf
AFB IIstatic void p(int n) {
if (n > 0) {
System.out.print(n);
p(n - 1);
System.out.print(n);
}
}Ermitteln Sie die vollständige Ausgabe des Aufrufs p(3).
Ansatz: Die erste Ausgabe steht vor dem Selbstaufruf (Abstieg), die zweite danach (Aufstieg).
Rechenweg: Abstieg: 3, 2, 1 werden sofort ausgegeben;
p(0) macht nichts; beim Aufstieg folgen 1, 2, 3.Lösung: 321123
Vollständige Lösung
Beim Abstieg druckt jeder Aufruf seinen Wert, bevor er wartet:
321. p(0) erfüllt die Bedingung n > 0 nicht und kehrt sofort zurück. Beim Aufstieg setzt jeder wartende Aufruf hinter dem Selbstaufruf fort — der zuletzt begonnene zuerst: 123. Gesamt: 321123. Anweisungen nach dem Selbstaufruf laufen also in umgekehrter Reihenfolge.A3
Terminiert das?
AFB II Trickstatic int f(int n) {
if (n == 0) {
return 0;
}
return 1 + f(n - 2);
}Untersuchen Sie die Methode: Geben Sie f(10) und die Anzahl der Aufrufe an. Für welche Eingaben endet die Rekursion nicht?
Ansatz: Der Parameter sinkt in Zweierschritten. Trifft er immer die 0?
Rechenweg: 10 → 8 → 6 → 4 → 2 → 0: sechs Aufrufe, fünfmal wird 1 addiert.
Lösung: a) 5 b) 6
Vollständige Lösung
f(10) = 1 + 1 + 1 + 1 + 1 + 0 = 5 nach 6 Aufrufen. Für ungerade n wird die 0 übersprungen (…, 3, 1, −1, −3, …): Die Abbruchbedingung wird nie erreicht, die Aufrufe laufen bis zum StackOverflowError. Dasselbe gilt für negative n. Abhilfe: Abbruch bei n <= 0 oder die Voraussetzung „n gerade und ≥ 0“ festlegen.