Informatik · Klasse 10

Ideen für aktives Lernen

Rekursion

Aktive Methoden wie Pair Programming oder Visualisierungen helfen Schülerinnen und Schülern, die abstrakte Idee der Rekursion konkret zu begreifen, da sie den Prozess des Selbstaufrufs und die Bedeutung des Basisfalls selbst erleben. Durch das Erforschen von Beispielen wie Fakultätsberechnung oder Fraktalzeichnung wird der Transfer von der Theorie zur Anwendung möglich.

• KMK Bildungsstandards
• KMK: STD.01
• KMK: STD.03

• 25–40 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• Museumsgang
• 30 Min. · Partnerarbeit

Pair Programming: Rekursive Fakultät

Paare implementieren eine rekursive Funktion zur Fakultätsberechnung in Python. Sie testen mit kleinen Werten, fügen den Basisfall ein und beobachten Ausgaben. Diskutieren Sie anschließend Iteration vs. Rekursion.

Wie zerlegt man ein Problem in identische, kleinere Teilprobleme?

Moderationstipp

Fordern Sie die Paare auf, den Code der rekursiven Fakultätsfunktion Zeile für Zeile gemeinsam zu durchlaufen und die Werte in einer Tabelle festzuhalten.

Worauf zu achten ist

Geben Sie jeder Schülerin und jedem Schüler eine kleine Karte. Bitten Sie sie, eine einfache rekursive Funktion (z.B. Fakultät) zu schreiben und den ersten rekursiven Aufruf sowie den Basisfall zu identifizieren. Notieren Sie auf der Rückseite, was passiert, wenn der Basisfall fehlt.

• Verstehen
• Anwenden
• Analysieren
• Erschaffen
• Beziehungsfähigkeit
• Sozialbewusstsein

Aktivität 02

• Museumsgang
• 25 Min. · Kleingruppen

Small Groups: Rekursionsbaum visualisieren

Gruppen zeichnen den Aufrufbaum für Fibonacci-Zahlen bis n=5 auf Papier. Markieren Sie Basisfälle und Rückkehrwerte. Vergleichen Sie mit Code-Ausführung in einer IDE.

Was ist die Gefahr eines Stack Overflow?

Moderationstipp

Geben Sie den Gruppen vor, den Rekursionsbaum nicht nur zu zeichnen, sondern auch die Anzahl der Aufrufe und die Tiefe zu notieren.

Worauf zu achten ist

Zeigen Sie eine kurze rekursive Funktion auf dem Beamer. Stellen Sie folgende Fragen: 'Welches Problem löst diese Funktion?', 'Was ist der Basisfall?', 'Was wäre der nächste rekursive Aufruf, wenn die Eingabe 5 wäre?'

• Verstehen
• Anwenden
• Analysieren
• Erschaffen
• Beziehungsfähigkeit
• Sozialbewusstsein

Aktivität 03

• Museumsgang
• 35 Min. · Ganze Klasse

Whole Class: Stack Overflow simulieren

Die Klasse simuliert rekursive Aufrufe mit Kartenstapeln: Jede Karte ist ein Frame. Fügen Sie Karten hinzu, bis der Stapel 'überläuft'. Diskutieren Sie Abhilfe durch Tail-Rekursion.

In welchen Fällen ist Rekursion iterativen Lösungen überlegen?

Moderationstipp

Lassen Sie die Schülerinnen und Schüler die Simulation des Stacks zunächst mit kleinen Zahlen beginnen, bevor sie komplexere Fälle betrachten.

Worauf zu achten ist

Stellen Sie die Frage: 'In welchen Situationen wäre eine rekursive Lösung klarer und eleganter als eine iterative, und wann wäre das Gegenteil der Fall?' Lassen Sie die Schülerinnen und Schüler Beispiele aus ihren Programmierübungen oder bekannten Algorithmen anführen und begründen.

• Verstehen
• Anwenden
• Analysieren
• Erschaffen
• Beziehungsfähigkeit
• Sozialbewusstsein

Aktivität 04

• Museumsgang
• 40 Min. · Einzelarbeit

Individual: Fraktal zeichnen

Jede Schülerin und jeder Schüler programmiert eine einfache rekursive Turtle-Grafik, z. B. ein Sierpinski-Dreieck. Testen und modifizieren Sie Parameter für Tiefe.

Wie zerlegt man ein Problem in identische, kleinere Teilprobleme?

Moderationstipp

Zeigen Sie vorab ein einfaches Fraktal (z.B. Sierpinski-Dreieck) und bitten Sie die Lernenden, die rekursive Struktur darin zu erkennen.

Worauf zu achten ist

Geben Sie jeder Schülerin und jedem Schüler eine kleine Karte. Bitten Sie sie, eine einfache rekursive Funktion (z.B. Fakultät) zu schreiben und den ersten rekursiven Aufruf sowie den Basisfall zu identifizieren. Notieren Sie auf der Rückseite, was passiert, wenn der Basisfall fehlt.

• Verstehen
• Anwenden
• Analysieren
• Erschaffen
• Beziehungsfähigkeit
• Sozialbewusstsein

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit alltagsnahen Beispielen, die Rekursion intuitiv machen, wie z.B. der Suche in einem Ordnerbaum oder der Berechnung von Zinsen. Wichtig ist, den Basisfall als zentralen Bestandteil zu betonen, denn ohne ihn scheitert die Rekursion. Iterative Alternativen sollten erst danach thematisiert werden, um die Einzigartigkeit rekursiver Lösungen zu verdeutlichen. Vermeiden Sie es, Rekursion als bloße Technik zu unterrichten – vielmehr geht es um das Verständnis von Problemen als wiederkehrende Muster.

Am Ende sollten Lernende in der Lage sein, rekursive Funktionen zu entwerfen, Basisfälle zu identifizieren und die Vorteile sowie Grenzen der Rekursion gegenüber Iteration zu diskutieren. Sie erkennen die Struktur des Problems und können sie in kleinere, lösbare Teilprobleme zerlegen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Pair Programming-Aktivität zur rekursiven Fakultät achten Sie darauf, dass einige Teams den Basisfall vergessen und stattdessen endlose Rekursionen erzeugen. Unterbrechen Sie die Arbeit kurz und fragen Sie: 'Wann soll dieser Funktionsaufruf enden, wenn wir bei 0 oder 1 ankommen?'

  Nutzen Sie die Visualisierung des Rekursionsbaums in der Kleingruppenarbeit, um zu zeigen, wie der Basisfall die Aufrufe begrenzt. Fragen Sie die Gruppen: 'Welche Ebene des Baums stellt den Basisfall dar, und warum ist sie unverzichtbar?'

• Während der Visualisierung des Rekursionsbaums entsteht die Annahme, Rekursion sei immer langsamer. Bringen Sie die Diskussion auf Tail-Rekursion und zeigen Sie, wie der Compiler sie in Schleifen umwandelt.

  Simulieren Sie während der Stapel-Overflow-Simulation im Plenum, wie tief die Rekursion bei unterschiedlichen Eingaben geht. Fragen Sie: 'Bei welcher Eingabegröße wäre der Stack überlastet, und warum ist das bei Bäumen anders als bei linearen Problemen?'

• Bei der Stack-Overflow-Simulation im Plenum wird vermutet, dass Überläufe nur bei großen Eingaben auftreten. Machen Sie bewusst, dass die Tiefe der Rekursion entscheidend ist.

  Fordern Sie die Lernenden auf, während der Fraktal-Zeichnung den Code schrittweise auszuführen und die Rekursionstiefe zu beobachten. Fragen Sie: 'Wie viele Ebenen können Sie zeichnen, bevor der Stack wächst? Was passiert, wenn Sie die Tiefe begrenzen?'

---

In dieser Übersicht verwendete Methoden

• Museumsgang