Informatik · Klasse 9 · Algorithmen und komplexe Datenstrukturen · 1. Halbjahr

Einführung in Rekursion

Die Schülerinnen und Schüler verstehen das Prinzip der Rekursion und implementieren einfache rekursive Funktionen.

• KMK Bildungsstandards
• KMK: Sekundarstufe I - Algorithmen
• KMK: Sekundarstufe I - Problemlösen

Über dieses Thema

Rekursion ist ein zentrales Prinzip in der Informatik, bei dem eine Funktion sich selbst aufruft, um ein Problem in kleinere, ähnliche Unterprobleme zu zerlegen. Schülerinnen und Schüler der Klasse 9 lernen, den Basisfall und den rekursiven Fall zu unterscheiden. Ein einfaches Beispiel ist die Berechnung der Fakultät: fak(n) = n * fak(n-1) mit Basisfall fak(0) = 1. Sie implementieren solche Funktionen in einer Programmiersprache wie Python und beobachten, wie der Aufrufstapel entsteht.

Im Kontext der KMK-Standards zu Algorithmen und Problemlösen vergleichen die Lernenden rekursive mit iterativen Lösungen. Rekursion eignet sich für natürliche Problembäume wie Baumdurchläufe, birgt aber Risiken wie Stapelüberlauf bei zu tiefer Verschachtelung. Iterative Ansätze sind oft effizienter in Zeit und Speicher. Dies fördert das analytische Denken und die Wahl passender Strategien.

Aktives Lernen macht Rekursion greifbar, da Schüler durch eigenes Programmieren und Debuggen den Aufrufstapel erleben. Visuelle Tools wie Rekursionsbäume oder Step-by-Step-Simulationen vertiefen das Verständnis und machen abstrakte Prozesse konkret und nachvollziehbar.

Leitfragen

1. Erklären Sie das Konzept der Rekursion anhand eines einfachen Beispiels.
2. Analysieren Sie die Vor- und Nachteile rekursiver Algorithmen im Vergleich zu iterativen Lösungen.
3. Konstruieren Sie eine rekursive Funktion zur Lösung eines Problems wie der Fakultätsberechnung.

Lernziele

• Erklären Sie das Konzept der Rekursion anhand eines einfachen Beispiels wie der Fakultätsberechnung.
• Analysieren Sie die Vor- und Nachteile rekursiver Algorithmen im Vergleich zu iterativen Lösungen hinsichtlich Laufzeit und Speicherbedarf.
• Konstruieren Sie eine einfache rekursive Funktion in Python zur Lösung eines gegebenen Problems.
• Identifizieren Sie den Basisfall und den rekursiven Schritt in einer gegebenen rekursiven Definition.
• Demonstrieren Sie die Funktionsweise einer rekursiven Funktion durch Nachvollziehen des Aufrufstapels.

Bevor es losgeht

Grundlagen der Programmierung (Variablen, Datentypen, Schleifen)

Warum: Schüler müssen grundlegende Programmierkonzepte verstehen, um rekursive Funktionen implementieren und nachvollziehen zu können.

Funktionen und ihre Anwendung

Warum: Das Verständnis, wie Funktionen aufgerufen werden und Werte zurückgeben, ist essenziell für das Verständnis von Funktionsaufrufen, insbesondere von sich selbst.

Schlüsselvokabular

Rekursion	Ein Verfahren, bei dem eine Funktion sich selbst aufruft, um ein Problem zu lösen, indem sie es in kleinere, gleichartige Teilprobleme zerlegt.
Basisfall	Die Bedingung, die eine rekursive Funktion beendet, um eine Endlosschleife zu verhindern. Er definiert die einfachste Form des Problems, die direkt gelöst werden kann.
Rekursiver Schritt	Der Teil einer rekursiven Funktion, der das Problem auf eine einfachere Version desselben Problems reduziert und die Funktion sich selbst mit diesem kleineren Problem aufruft.
Aufrufstapel (Call Stack)	Eine Datenstruktur, die Informationen über aktive Unterprogrammaufrufe speichert. Bei Rekursion werden die einzelnen Funktionsaufrufe hier abgelegt, bis der Basisfall erreicht ist.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Rekursion führt immer zu einer Endlosschleife.

Was Sie stattdessen lehren sollten

Der Basisfall stoppt die Rekursion. Schüler entdecken dies durch schrittweises Debuggen in Paaren, wo sie Aufrufe manuell nachstellen und den Abbruch sehen. Aktive Tests mit Print-Anweisungen klären den Prozess.

Häufige Fehlvorstellung

Rekursive Lösungen sind immer eleganter und schneller.

Was Sie stattdessen lehren sollten

Rekursion kann ineffizient sein durch wiederholte Berechnungen. Gruppenvergleiche von Laufzeiten iterativer und rekursiver Varianten zeigen Speicher- und Zeitkosten. Diskussionen in der Klasse festigen die Abwägung.

Häufige Fehlvorstellung

Der Stapel wächst unendlich, egal wie.

Was Sie stattdessen lehren sollten

Tiefe ist begrenzt durch Problemgröße und Basisfall. Visuelle Simulationen mit Stapelmodellen in Gruppen machen Überlauf greifbar und lehren Optimierungen wie Memoization.

Ideen für aktives Lernen

Paarprogrammierung: Rekursive Fakultät

Paare schreiben eine rekursive Funktion für die Fakultät und testen sie mit Werten von 0 bis 5. Sie zeichnen den Aufrufstapel auf Papier nach und vergleichen mit einer iterativen Version. Abschließend diskutieren sie Laufzeiten.

30 Min.·Partnerarbeit

Stationenrotation: Rekursionsbeispiele

Richten Sie Stationen ein: Fakultät, Fibonacci, String-Umkehrung. Gruppen implementieren je eine Funktion, testen und erklären sie der nächsten Gruppe. Rotieren Sie alle 10 Minuten.

45 Min.·Kleingruppen

Ganzer Unterricht: Tower of Hanoi simulieren

Die Klasse simuliert Tower of Hanoi mit Bausteinen oder Karten. Jede Schülerin erklärt einen Zug rekursiv. Danach programmieren sie es digital und messen die Schritte.

50 Min.·Ganze Klasse

Individuell: Rekursiv vs. Iterativ

Jede Schülerin implementiert Fibonacci rekursiv und iterativ, misst Ausführungszeiten mit timeit. Sie notieren Vor- und Nachteile in einem Vergleichsprotokoll.

25 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• In der Computergrafik wird Rekursion verwendet, um fraktale Muster wie die Koch-Schneeflocke oder Bäume zu erzeugen, die in Filmen für Spezialeffekte oder in der Spieleentwicklung eingesetzt werden.
• Algorithmen zur Pfadfindung in komplexen Netzwerken, wie sie von Navigationssystemen oder Routenplanern (z. B. Google Maps) genutzt werden, können rekursive Ansätze verwenden, um den kürzesten oder effizientesten Weg zu finden.
• Die Struktur von Dateisystemen auf Computern, bei denen Ordner Unterordner enthalten können, wird oft rekursiv durchlaufen, um alle Dateien zu finden oder zu verwalten.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie den Schülerinnen und Schülern eine Karte mit der Definition der Fakultätsfunktion (fak(n) = n * fak(n-1), fak(0) = 1). Bitten Sie sie, den Basisfall und den rekursiven Schritt zu identifizieren und zu erklären, warum der Basisfall notwendig ist.

Kurze Überprüfung

Stellen Sie eine einfache rekursive Funktion (z.B. eine Funktion, die eine Zahl verdoppelt, bis sie 100 erreicht) auf dem Whiteboard dar. Bitten Sie die Schüler, die ersten drei Funktionsaufrufe und die entsprechenden Rückgabewerte aufzuzeichnen, um das Verständnis des Aufrufstapels zu prüfen.

Diskussionsfrage

Leiten Sie eine Diskussion: 'Stellen Sie sich vor, Sie müssten eine Funktion schreiben, die alle Elemente einer Liste umkehrt. Wann wäre eine rekursive Lösung hier besser geeignet als eine iterative? Wann wäre sie schlechter geeignet? Nennen Sie konkrete Gründe.'

Häufig gestellte Fragen

Was ist Rekursion einfach erklärt für Klasse 9?

Rekursion bedeutet, dass eine Funktion sich selbst aufruft, um ein Problem kleiner zu lösen, bis ein einfacher Basisfall erreicht ist. Beispiel: Fakultät n! = n * (n-1)!, mit fak(0)=1. Schüler implementieren es und sehen den Aufrufbaum. Dies passt zu KMK-Standards für Algorithmen und baut Problemlösefähigkeiten auf. Visuelle Hilfen wie Diagramme erleichtern den Einstieg.

Wie implementiert man eine rekursive Fakultät in Python?

Definiere def fak(n): if n == 0: return 1 else: return n * fak(n-1). Teste mit print(fak(5)), erwarte 120. Füge Prints hinzu, um Rekursionstiefe zu sehen. Vergleiche mit Schleife: res=1; for i in range(1,n+1): res*=i. Diskutiere Stapelrisiken bei großen n.

Wie kann aktives Lernen Rekursion verständlich machen?

Aktives Programmieren in Paaren lässt Schüler den Aufrufstapel selbst erleben, z.B. durch Debuggen mit Prints. Stationen mit Beispielen wie Fibonacci fördern Erklären und Testen. Whole-Class-Simulationen von Tower of Hanoi verbinden Physisches mit Digitalem. Solche Methoden machen Abstraktes konkret, reduzieren Ängste und verbessern Retention um bis zu 50 Prozent.

Vorteile und Nachteile rekursiver Algorithmen?

Vorteile: Elegante Lösung für fraktale oder baumartige Probleme, kürzerer Code. Nachteile: Höherer Speicherverbrauch durch Stapel, Risiko von Überlauf, oft langsamere Laufzeit durch Redundanz. Iterative Varianten sind effizienter für lineare Probleme. Schüler analysieren dies durch Messungen, was Entscheidungsfähigkeiten schult.