MINT lernen

Übungen: Das Prinzip Rekursion

Zehn Übungen zur Rekursion — vom Erkennen der Abbruchbedingung bis zum Urteil, ob eine Methode terminiert.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt dir sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.

A1
Was jede Rekursion braucht
AFB I

Gib alle Aussagen an, die auf jede korrekte rekursive Methode zutreffen.

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Abbruchbedingung, Selbstaufruf mit verändertem Parameter und die Garantie, dass die Abbruchbedingung erreicht wird — mehr braucht es nicht. Die Abbruchbedingung kann jede Form haben (n < 10, s.length() == 0 …), und eine Methode darf sich auch zweimal aufrufen.
Ansatz: Denk an die drei Bedingungen für Terminierung aus der Erklärung.
Weiter: Eine Schleife ist bei Rekursion gerade nicht nötig — die Wiederholung entsteht durch den Selbstaufruf.
A2
Stimmt's? — Sternenreihe
AFB I

Gegeben ist die Methode sterne. Lies aus dem Quelltext ab, ob die Aussagen stimmen.

static int sterne(int n) {
    if (n <= 0) return 0;
    return 3 + sterne(n - 1);
}
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Wer n <= 0 statt n == 0 schreibt, schützt die Methode vor negativen Eingaben.
Ansatz: Suche zuerst die Zeile ohne Selbstaufruf.
Weiter: Der Parameter im Selbstaufruf ist n - 1; die 3 steht außerhalb des Aufrufs.
A3
Abbruch oder Schritt?
AFB I

Ordne jede Zeile aus verschiedenen rekursiven Methoden richtig zu.

Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Abbruchbedingung
2Rekursionsschritt
Erkennungszeichen: Die Abbruchbedingung liefert ein Ergebnis ohne Selbstaufruf, der Rekursionsschritt enthält den Namen der eigenen Methode. Bei rauf wächst der Parameter — trotzdem endet die Rekursion, weil k > 100 irgendwann erreicht wird.
Ansatz: Enthält die Zeile den Namen der Methode, in der sie steht?
Weiter: Zeilen mit if und direkter Rückgabe sind Abbruchbedingungen.
A4
Werte einer rekursiven Methode
AFB II

Berechne die Rückgabewerte der Methode w schrittweise.

static int w(int n) {
    if (n == 1) return 5;
    return w(n - 1) * 2 - 3;
}
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. w(2) =
  2. w(3) =
  3. w(4) =
  4. Anzahl der Aufrufe von w bei w(4): Aufrufe
Von unten nach oben rechnen spart Arbeit: w(1) = 5, w(2) = 5 · 2 − 3 = 7, w(3) = 7 · 2 − 3 = 11, w(4) = 11 · 2 − 3 = 19. Der Aufruf w(4) löst w(3), w(2) und w(1) aus — zusammen 4 Aufrufe.
Ansatz: Beginne bei der Abbruchbedingung: w(1) = 5.
Weiter: Jeder Wert ist das Doppelte des vorigen minus 3.
A5
Countdown
AFB II

Die Methode countdown(3) soll 3, 2, 1 und dann Start! ausgeben. Erstelle die rekursive Methode, indem du die Zeilen ordnest.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1static void countdown(int n) {
2 if (n == 0) {
3 System.out.println("Start!");
4 } else {
5 System.out.println(n);
6 countdown(n - 1);
7 } // Ende else
8} // Ende der Methode
Die Ausgabe von n steht vor dem Selbstaufruf — deshalb erscheinen die Zahlen absteigend. Vertauscht man die beiden Zeilen, erscheint zuerst „Start!“ und dann 1, 2, 3: Die Ausgaben werden erst beim Rücklauf ausgeführt.
Ansatz: Eine void-Methode braucht kein return — der Basisfall gibt nur „Start!“ aus.
Weiter: Welche Zahl soll zuerst erscheinen? Dann muss ihre Ausgabe vor dem Selbstaufruf stehen.
A6
Einsen im Binärsystem
AFB II Mix

Die Methode r nutzt Division und Rest aus Kapitel 1. Bestimme für jeden Aufruf den Rückgabewert.

static int r(int n) {
    if (n == 0) return 0;
    return n % 2 + r(n / 2);
}
Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
n % 2 ist die letzte Binärziffer, n / 2 schneidet sie ab. r zählt also die Einsen der Binärdarstellung: 8 = 1000₂ hat eine Eins, 5 = 101₂ zwei, 7 = 111₂ drei, 15 = 1111₂ vier.
Ansatz: Schreibe r(5) aus: 5 % 2 + r(2), dann 2 % 2 + r(1), dann 1 % 2 + r(0).
Weiter: n / 2 ist ganzzahlige Division: 5 / 2 = 2.
A7
Zweierpotenzen mit Fehlern
AFB II

Die Methode soll \(2^n\) für \(n \ge 0\) berechnen. Überprüfe sie Zeile für Zeile.

In diesem Quelltext stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Zwei Fehler: Der einfachste Fall ist \(n = 0\) mit \(2^0 = 1\), und der Schritt verdoppelt statt 2 zu addieren. Prüfe Rekursionen immer mit dem kleinsten zulässigen Wert.
Ansatz: Setze n = 0 und n = 3 ein und vergleiche mit 1 bzw. 8.
Weiter: Zwei Zeilen sind falsch — eine in der Abbruchbedingung, eine im Rekursionsschritt.
A8
Aufwärts zum Ziel
AFB III Trick

Ermittle den Rückgabewert von t(3).

static int t(int n) {
    if (n > 20) return n;
    return t(n * 2);
}
Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
Aufrufkette: t(3) → t(6) → t(12) → t(24). Bei 24 ist n > 20 wahr, zurückgegeben wird 24. Der Parameter wird größer — trotzdem endet die Rekursion, weil sie sich der Abbruchbedingung n > 20 nähert. Vorsicht bei t(0): 0 · 2 bleibt 0, dieser Aufruf endet nie.
Ansatz: Verfolge die Aufrufkette: Welche Parameter entstehen?
Weiter: „Näher an die Abbruchbedingung“ heißt hier: größer werden.
A9
Terminiert das?
AFB III

Beurteile für jede Methode, für welche Eingaben \(n \ge 0\) sie terminiert.

Setze in jeder Zeile das passende Kreuz — hier ist es genau eins pro Zeile. Enter setzt und löscht.
Methodefür alle n ≥ 0nur für manche n ≥ 0für kein n ≥ 0
a: if (n == 0) return 0; return a(n - 1) + 1;
b: if (n == 10) return 0; return b(n + 1);
c: if (n == 0) return 1; return c(n) * 2;
d: if (n < 0) return 0; return d(n + 1);
e: if (n <= 1) return n; return e(n / 2);
b endet nur für \(n \le 10\), c nur für \(n = 0\) — sonst ruft sie sich mit demselben Parameter auf. d startet bei \(n \ge 0\) und wächst, erreicht \(n < 0\) also nie. e halbiert, bis 1 oder 0 erreicht ist.
Ansatz: Setze für jede Methode ein kleines und ein großes n ein.
Weiter: Achte auf Methoden, bei denen sich der Parameter gar nicht ändert oder von der Abbruchbedingung wegläuft.
A10
Eine Summe rekursiv entwickeln
AFB III

Entwickle Schritt für Schritt eine rekursive Methode summeGerade(n), die \(2 + 4 + \dots + 2n\) berechnet.

Spiele den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
    Rezept für jede rekursive Methode: einfachsten Fall festlegen, Zusammenhang zum nächstkleineren Problem finden, Teilergebnis verwenden, mit einem Beispiel prüfen, Terminierung begründen.
    Ansatz: Beginne immer mit dem einfachsten Fall.
    Weiter: Schreibe die Summe für n = 3 aus: 2 + 4 + 6. Welcher Teil davon ist summeGerade(2)?