04 Prüfungsvorbereitung

Einstieg in das Thema

Was brauchst du als Basiswissen?

Du solltest Rekursion an Bildern und Handlungen erklären können. Außerdem solltest du Grundfall, Rekursionsschritt, Abbruchbedingung und Generation unterscheiden können.

Worum geht es?

In der Prüfung gibt es kurze Wissensfragen der Stufe 1 sowie Verständnis-, Vervollständigungs- und Regelaufgaben der Stufe 2. Die Beispiele hier sind nicht mit den Prüfungsfragen identisch.

Was ist das Ziel?

Du kannst rekursive Strukturen erkennen, Regeln genau anwenden und deine Entscheidungen verständlich begründen.

Erarbeitung

Stufe 1 – Beispiel mit Lösung

Was unterscheidet Grundfall und Rekursionsschritt?

Lösung: Der Grundfall legt die einfachste Struktur und den Startwert fest. Der Rekursionsschritt beschreibt dieselbe Struktur mithilfe einer kleineren Stufe oder erzeugt daraus die nächste Stufe.

Stufe 1 – Aufgabe ohne Lösung

Erkläre jeweils in einem Satz:

Aufgabe 1
rekursiv
Aufgabe 2
Abbruchbedingung
Aufgabe 3
Generation
Aufgabe 4
selbstähnlich

Stufe 2 – Beispiel mit Lösung

Es gilt:

R(0) = ein Ring R(n) = ein Ring um R(n−1), wenn n mindestens 1 ist.

Löse R(3) auf und gib die Anzahl der Ringe an.

Lösung:

R(3) = Ring + R(2) = Ring + Ring + R(1) = Ring + Ring + Ring + R(0) = vier Ringe

Beim Auflösen arbeiten wir rückwärts bis zum Grundfall R(0). Zum Zeichnen lesen wir das Ergebnis anschließend vom Grundfall aus vorwärts.

Stufe 2 – Aufgabe ohne Lösung

Es gilt:

D(0) = ein Dreieck D(n) = ein Dreieck neben D(n−1), wenn n mindestens 1 ist.

Aufgabe 5
Löse D(4) schrittweise auf.
Aufgabe 6
Wie viele Dreiecke enthält D(4)?
Aufgabe 7
Kennzeichne Grundfall und Rekursionsschritt.
Aufgabe 8
Beschreibe beide Blickrichtungen: Auflösen und Konstruieren.

Weitere Übungen ohne Lösung

Aufgabe 9
Entscheide und begründe, welche Beispiele rekursiv sind: eine Perlenkette aus gleichen Perlen; ein Ast, dessen kleinere Äste sich auf dieselbe Weise teilen; fünf kopierte Kreise nebeneinander; ein Bild, das eine kleinere Kopie von sich enthält.
Aufgabe 10
Ein Quadrat mit 24 cm Seitenlänge enthält jeweils ein halb so großes Quadrat. Wiederholt wird nur, solange die neue Seitenlänge mindestens 1,5 cm beträgt. Notiere alle Größen und bestimme die Zahl der Rekursionsschritte.
Aufgabe 11
Start B, Regeln A→BA und B→AB. Erzeuge die Generationen 0 bis 4. Markiere, welche Zeichen einer Generation welchen Ersatz in der nächsten Generation erzeugen.
Aufgabe 12
Start A, Regeln A→ABC, B→B und C→A. Erzeuge drei Generationen. Erkläre dabei, was mit B geschieht.
Aufgabe 13
Erfinde ein System mit Start und höchstens zwei Zeichenregeln. Es soll in jeder Generation länger werden. Erzeuge vier Generationen und begründe das Wachstum.
Aufgabe 14
Zeichne die Stufen 0 bis 2 eines Sierpinski-Dreiecks. Markiere Start, wiederholte Regel und eine mögliche Abbruchbedingung.
Aufgabe 15
Eine Person behauptet: „Jede Wiederholung ist Rekursion.“ Formuliere ein Gegenbeispiel und verbessere die Aussage.
Aufgabe 16
Start F, Regel F→F−F+F; die Zeichen + und − bleiben stehen. Erzeuge Generation 1 und 2. Beschreibe, wie daraus später mit Zeichenbefehlen ein Bild entstehen könnte.

Rückblick

Was solltest du vor der Prüfung können?

  • Rekursion in eigenen Worten erklären
  • rekursive und nichtrekursive Beispiele unterscheiden
  • Grundfall, Rekursionsschritt und Abbruchbedingung unterscheiden
  • T(n) schrittweise bis T(0) auflösen
  • eine Folge vom Grundfall aus vorwärts lesen
  • Zeichenregeln gleichzeitig auf eine Generation anwenden
  • Sierpinski-Stufen beschreiben und fortsetzen
  • aus Start und Regel eigene Generationen erzeugen

Prüfe bei Zeichenersetzungen jedes Zeichen einzeln. Schreibe die vollständige alte Generation über die neue, bevor du weitergehst.