MINT lernen

Abituraufgaben: Das Prinzip Rekursion

Zwei Aufgaben im Abiturformat — von Sitzreihen im Theater bis zur ungelösten Collatz-Vermutung.

Dein Fortschritt:
0 / 0 Aufgaben
1

Sitzreihen im Theater

AFB I–II

Im Parkett eines Theaters hat die vorderste Reihe 12 Plätze, jede weitere Reihe 2 Plätze mehr. Das Kassensystem berechnet die Platzzahlen mit den abgebildeten Methoden: plaetze(r) liefert die Zahl der Plätze in Reihe r, gesamt(r) die Zahl der Plätze in den Reihen 1 bis r.

Material: Methoden des Kassensystems
static int plaetze(int r) {
    if (r == 1) {
        return 12;
    }
    return plaetze(r - 1) + 2;
}

static int gesamt(int r) {
    if (r == 0) {
        return 0;
    }
    return plaetze(r) + gesamt(r - 1);
}
  1. Beschreiben Sie für die Methode plaetze die Abbruchbedingung und den Rekursionsschritt und deren Bedeutung im Sachzusammenhang. 3 BE
  2. Bestimmen Sie die Rückgabewerte von plaetze(4) und gesamt(3). Stellen Sie dabei die Auswertung der Aufrufe schrittweise dar. 5 BE
  3. Untersuchen Sie, was beim Aufruf plaetze(0) geschieht, und verändern Sie die Methode so, dass sie für alle \(r \le 0\) den Wert 0 liefert. 4 BE
  4. Zeigen Sie, dass plaetze(r) für alle \(r \ge 1\) den Wert \(10 + 2r\) liefert. 4 BE

Insgesamt 16 BE

Hinweise

Hinweis zu Aufgabe a)
Die Abbruchbedingung ist die Zeile ohne Selbstaufruf. Was bedeutet „Reihe 1“ im Theater?
Hinweis zu Aufgabe b)
Schreiben Sie die Aufrufe untereinander, bis die Abbruchbedingung greift, und rechnen Sie dann rückwärts.
Hinweis zu Aufgabe c)
Welche Parameter entstehen ausgehend von 0? Wird die Abbruchbedingung r == 1 je erreicht?
Hinweis zu Aufgabe d)
Argumentieren Sie wie bei einer vollständigen Induktion: Gilt es für \(r = 1\), und folgt es für \(r\) aus \(r - 1\)?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Abbruchbedingung r == 1: Die vorderste Reihe hat 12 Plätze, dieser Wert wird ohne Selbstaufruf zurückgegeben. Rekursionsschritt plaetze(r - 1) + 2: Reihe \(r\) hat 2 Plätze mehr als die Reihe davor; die Platzzahl der vorderen Reihe wird durch den Selbstaufruf mit \(r - 1\) ermittelt.

Erwartungshorizont zu Aufgabe b)

\(\text{plaetze}(4) = \text{plaetze}(3) + 2 = \text{plaetze}(2) + 2 + 2 = \text{plaetze}(1) + 2 + 2 + 2 = 12 + 6 = 18\).

\(\text{gesamt}(3) = \text{plaetze}(3) + \text{gesamt}(2) = 16 + \text{plaetze}(2) + \text{gesamt}(1) = 16 + 14 + \text{plaetze}(1) + \text{gesamt}(0) = 16 + 14 + 12 + 0 = 42\).

Erwartungshorizont zu Aufgabe c)

plaetze(0) ruft plaetze(-1), plaetze(-2), … auf; der Parameter entfernt sich von 1, die Abbruchbedingung wird nie erreicht. Nach sehr vielen offenen Aufrufen bricht das Programm mit einem StackOverflowError ab.

static int plaetze(int r) {
    if (r <= 0) {
        return 0;
    }
    if (r == 1) {
        return 12;
    }
    return plaetze(r - 1) + 2;
}

Die zusätzliche Abbruchbedingung muss vor dem Selbstaufruf stehen.

Erwartungshorizont zu Aufgabe d)

Für \(r = 1\) liefert die Methode 12 \(= 10 + 2 \cdot 1\). Gilt für \(r - 1\) (mit \(r \ge 2\)) bereits \(\text{plaetze}(r-1) = 10 + 2(r-1)\), so liefert der Rekursionsschritt \(10 + 2(r-1) + 2 = 10 + 2r\). Da jeder Aufruf mit \(r \ge 2\) auf \(r - 1\) zurückgeführt wird und schließlich bei \(r = 1\) ankommt, gilt die Formel für alle \(r \ge 1\).

2

Die Collatz-Folge

AFB II–III

Bei der Collatz-Folge wird eine positive ganze Zahl halbiert, wenn sie gerade ist, und sonst durch \(3n + 1\) ersetzt. Es wird vermutet, dass man von jeder Startzahl aus irgendwann bei 1 ankommt; bewiesen ist das bis heute nicht. Die Methode schritte zählt die Schritte bis zur 1.

Material: Methode schritte
static int schritte(int n) {
    if (n == 1) {
        return 0;
    }
    if (n % 2 == 0) {
        return 1 + schritte(n / 2);
    }
    return 1 + schritte(3 * n + 1);
}
  1. Analysieren Sie den Aufruf schritte(6), indem Sie die Folge der Aufrufe angeben und den Rückgabewert bestimmen. 4 BE
  2. Erläutern Sie, warum der Aufruf schritte(0) nicht terminiert. 2 BE
  3. Beurteilen Sie die Aussage: „Weil der Parameter nicht bei jedem Aufruf kleiner wird, kann schritte gar nicht terminieren.“ 4 BE
  4. Implementieren Sie eine Methode schritte(int n, int max), die dasselbe liefert wie schritte(n), jedoch −1 zurückgibt, sobald mehr als max Schritte nötig wären. Die Methode soll für jede Eingabe terminieren. 6 BE

Insgesamt 16 BE

Hinweise

Hinweis zu Aufgabe a)
Unterscheiden Sie in jedem Aufruf: gerade oder ungerade?
Hinweis zu Aufgabe b)
Welche Abbruchbedingung müsste erreicht werden, und welchen Parameter erzeugt der Aufruf mit 0?
Hinweis zu Aufgabe c)
Trennen Sie „Parameter wird kleiner“ von „Abbruchbedingung wird erreicht“. Ein Gegenbeispiel genügt, um die Aussage zu widerlegen.
Hinweis zu Aufgabe d)
Der zweite Parameter zählt die noch erlaubten Schritte herunter und liefert eine zweite Abbruchbedingung. Das −1 muss durch alle wartenden Aufrufe hindurchgereicht werden.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Aufrufe: schritte(6) → schritte(3) → schritte(10) → schritte(5) → schritte(16) → schritte(8) → schritte(4) → schritte(2) → schritte(1). Der letzte Aufruf liefert 0, jeder der acht wartenden Aufrufe addiert 1: Rückgabewert 8.

Erwartungshorizont zu Aufgabe b)

0 ist gerade, also folgt schritte(0 / 2) = schritte(0). Der Parameter ändert sich nicht, die Abbruchbedingung n == 1 wird nie erreicht. Die Aufrufe stapeln sich, bis ein StackOverflowError auftritt.

Erwartungshorizont zu Aufgabe c)

Die Aussage ist falsch. Für Terminierung ist entscheidend, dass die Abbruchbedingung nach endlich vielen Aufrufen erreicht wird, nicht dass der Parameter stets sinkt. Gegenbeispiel: schritte(6) terminiert, obwohl der Parameter von 3 auf 10 und von 5 auf 16 steigt. Richtig ist allerdings, dass sich die Terminierung hier nicht allgemein begründen lässt: Ob jede Startzahl die 1 erreicht, ist die unbewiesene Collatz-Vermutung. Die Methode terminiert für alle bisher getesteten Zahlen, eine Garantie gibt es nicht.

Erwartungshorizont zu Aufgabe d)
static int schritte(int n, int max) {
    if (n == 1) {
        return 0;
    }
    if (max == 0) {
        return -1;                       // Grenze erreicht
    }
    int rest;
    if (n % 2 == 0) {
        rest = schritte(n / 2, max - 1);
    } else {
        rest = schritte(3 * n + 1, max - 1);
    }
    if (rest == -1) {
        return -1;                       // Abbruch weiterreichen
    }
    return 1 + rest;
}

Beispiele: schritte(6, 8) liefert 8, schritte(6, 7) liefert −1. Weil max bei jedem Aufruf um 1 sinkt, endet die Rekursion spätestens nach max + 1 Aufrufen — auch für n = 0.