Informatik · Klasse 12 · Datenstrukturen und Algorithmen · 1. Halbjahr

Rekursion und Iteration

Die Schülerinnen und Schüler vergleichen rekursive und iterative Lösungsansätze für Probleme und analysieren deren Vor- und Nachteile.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Modellieren und Implementieren
• KMK: Sekundarstufe II - Problemlösen und Handeln

Über dieses Thema

Das Thema Rekursion und Iteration vertieft das Verständnis algorithmischer Problemlösungen in der Oberstufe. Schülerinnen und Schüler vergleichen rekursive Verfahren, bei denen Funktionen sich selbst aufrufen, mit iterativen Schleifenansätzen. Sie analysieren Vor- und Nachteile bezüglich Lesbarkeit, Speicherverbrauch und Laufzeit, etwa bei der Fakultätsberechnung oder der Fibonacci-Folge. Rekursive Lösungen spiegeln natürliche Strukturen wider, wie Bäume oder Fraktale, erfordern jedoch Basisfälle, um Endlosschleifen zu vermeiden.

Die Inhalte knüpfen an KMK-Standards zu Modellieren, Implementieren und Problemlösen an. Schüler konstruieren Algorithmen in Python oder Java, debuggen Stack-Overflow-Fehler und bewerten Effizienz durch Messungen. Iterative Varianten sind speichersparender und skalierbarer für große Eingaben, während Rekursion die Eleganz mathematischer Modelle betont. Diese Analyse fördert systematisches Denken und Transfer auf reale Anwendungen wie Graph-Algorithmen.

Aktives Lernen eignet sich hervorragend, weil Schüler durch Pair Programming und experimentelle Implementierungen abstrakte Konzepte erleben. Sie vergleichen Laufzeiten selbst, visualisieren Aufrufstapel und diskutieren Trade-offs, was Motivation steigert und bleibendes Verständnis schafft.

Leitfragen

1. Differentiieren Sie zwischen rekursiven und iterativen Algorithmen.
2. Analysieren Sie die Vor- und Nachteile von Rekursion hinsichtlich Speicherverbrauch und Lesbarkeit.
3. Konstruieren Sie eine rekursive Lösung für ein Problem wie die Fakultätsberechnung.

Lernziele

• Analysieren Sie die Speicher- und Laufzeitunterschiede zwischen rekursiven und iterativen Implementierungen der Fakultätsberechnung.
• Vergleichen Sie die Lesbarkeit und Eleganz von rekursiven und iterativen Lösungen für die Fibonacci-Folge.
• Konstruieren Sie eine rekursive Funktion zur Lösung eines gegebenen Problems, z.B. der Umkehrung einer Zeichenkette.
• Bewerten Sie, wann eine rekursive Lösung aufgrund von Stack-Overflow-Risiken ungeeignet ist.
• Erklären Sie die Rolle des Basisfalls in einer rekursiven Funktion.

Bevor es losgeht

Grundlagen der Programmierung (Variablen, Datentypen, Kontrollstrukturen)

Warum: Schüler müssen grundlegende Programmierkonzepte beherrschen, um Funktionen, Schleifen und bedingte Anweisungen zu verstehen und anzuwenden.

Funktionen und ihre Anwendung

Warum: Das Verständnis von Funktionsdefinition, Aufruf und Rückgabewerten ist essenziell für das Verständnis von Rekursion, bei der Funktionen sich selbst aufrufen.

Schlüsselvokabular

Rekursion	Ein Lösungsansatz, bei dem eine Funktion sich selbst aufruft, um ein Problem zu lösen, typischerweise mit einem Basisfall zur Beendigung.
Iteration	Ein Lösungsansatz, der wiederholte Ausführung von Codeblöcken mittels Schleifen (wie for oder while) verwendet, um ein Problem zu lösen.
Basisfall	Die Bedingung in einer rekursiven Funktion, die den Abbruch der Rekursion sicherstellt und eine direkte Rückgabe ohne weiteren rekursiven Aufruf ermöglicht.
Aufrufstapel (Call Stack)	Eine Datenstruktur, die Informationen über aktive Unterprogrammaufrufe speichert; bei Rekursion kann dieser bei tiefen Aufrufen überlaufen (Stack Overflow).
Laufzeitkomplexität	Ein Maß dafür, wie die Ausführungszeit eines Algorithmus mit der Größe der Eingabe wächst, oft ausgedrückt in Big-O-Notation.
Speicherkomplexität	Ein Maß dafür, wie der Speicherbedarf eines Algorithmus mit der Größe der Eingabe wächst.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Rekursion ist immer effizienter als Iteration.

Was Sie stattdessen lehren sollten

Rekursion verbraucht oft mehr Speicher durch den Aufrufstapel und kann exponentiell langsam sein, wie bei naiver Fibonacci. Pair Programming mit Zeitmessungen hilft Schülern, dies empirisch zu erkennen und iterative Optimierungen zu entwickeln.

Häufige Fehlvorstellung

Rekursive Funktionen brauchen keinen Basisfall.

Was Sie stattdessen lehren sollten

Ohne Basisfall entsteht eine Endlosschleife. Aktive Simulationen mit Stapelmodellen lassen Schüler den Fehler live nachstellen und korrigieren, was das Verständnis für Termination vertieft.

Häufige Fehlvorstellung

Iteration ist immer weniger lesbar.

Was Sie stattdessen lehren sollten

Iteration kann kompakt sein, Rekursion natürlicher für hierarchische Probleme. Gruppenvergleiche fördern Nuancenwahrnehmung durch gegenseitige Code-Reviews.

Ideen für aktives Lernen

Pair Programming: Fakultätsvergleich

Paare coden die Fakultät rekursiv und iterativ in Python. Sie testen mit großen Werten, messen Zeit und Speicher mit timeit. Gemeinsam listen sie Vor- und Nachteile auf.

30 Min.·Partnerarbeit

Small Groups: Fibonacci-Analyse

Gruppen implementieren Fibonacci rekursiv, memoisiert und iterativ. Sie zeichnen den Rekursionsbaum und vergleichen Ausführungszeiten. Ergebnisse werden in einer Tabelle dokumentiert.

45 Min.·Kleingruppen

Whole Class: Stack-Visualisierung

Die Klasse simuliert rekursive Aufrufe mit Kartenstapeln für Hanoi-Türme. Jeder Schritt wird auf dem Beamer gezeigt, Diskussion folgt zu Overflow-Risiken.

25 Min.·Ganze Klasse

Individual: Code-Review

Jede Schülerin und jeder Schüler schreibt eine rekursive Funktion, tauscht mit einem Partner und bewertet Lesbarkeit sowie Iterationspotenzial.

20 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• In der Computergrafik werden rekursive Algorithmen zur Erzeugung komplexer Muster wie Fraktale (z.B. Sierpinski-Dreieck) verwendet, die in der Animation und bei der Darstellung realistischer Landschaften zum Einsatz kommen.
• Betriebssysteme nutzen rekursive Ansätze für die Verwaltung von Dateisystemhierarchien, um Verzeichnisse und Unterverzeichnisse effizient zu durchsuchen und zu organisieren.
• Compiler verwenden rekursive Abstiegsparser, um die Syntax von Programmiersprachen zu analysieren und Code in maschinenlesbare Anweisungen zu übersetzen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie den Lernenden eine einfache rekursive Funktion (z.B. Fakultät) und eine iterative Funktion mit identischer Funktionalität. Bitten Sie sie, auf einem Zettel zu notieren: 1. Welcher Ansatz ist für sie leichter zu verstehen? 2. Nennen Sie einen Nachteil des jeweils anderen Ansatzes.

Kurze Überprüfung

Stellen Sie die Frage: 'Stellen Sie sich vor, Sie müssten die Fibonacci-Zahlen bis 1000 berechnen. Würden Sie eine rekursive oder eine iterative Lösung bevorzugen und warum? Begründen Sie Ihre Wahl unter Berücksichtigung von Speicher und Geschwindigkeit.'

Diskussionsfrage

Teilen Sie die Klasse in zwei Gruppen: 'Rekursion-Befürworter' und 'Iteration-Befürworter'. Geben Sie jeder Gruppe 5 Minuten Zeit, Argumente für ihren bevorzugten Ansatz zu sammeln. Führen Sie anschließend eine kurze Debatte, in der jede Gruppe die Vorteile ihres Ansatzes darlegt und auf die Argumente der Gegenseite eingeht.

Häufig gestellte Fragen

Was sind Vor- und Nachteile von Rekursion gegenüber Iteration?

Rekursion bietet hohe Lesbarkeit für Probleme mit natürlicher Selbstähnlichkeit, wie Baumtraversierungen, verbraucht jedoch Stack-Speicher und riskiert Overflow bei tiefer Rekursion. Iteration spart Speicher, ist vorhersagbarer und effizienter für lineare Aufgaben wie Summen. Schüler lernen durch Implementierungsvergleiche, wann welcher Ansatz passt, und messen reale Unterschiede in der Praxis.

Wie berechnet man die Fakultät rekursiv?

Die rekursive Fakultät definiert n! = n * (n-1)! mit Basisfall 0! = 1. In Python: def fak(n): if n <= 1: return 1 else: return n * fak(n-1). Schüler testen Grenzfälle und optimieren iterativ, um Speicherverbrauch zu verstehen und Robustheit zu gewährleisten.

Wie kann aktives Lernen Rekursion und Iteration vermitteln?

Pair Programming lässt Schüler beide Ansätze coden, messen und debuggen, was abstrakte Konzepte konkretisiert. Gruppenvisualisierungen von Rekursionsbäumen und Klassen-Diskussionen zu Trade-offs fördern Peer-Learning. Solche Methoden steigern Engagement, reduzieren Fehlvorstellungen und verbinden Theorie mit eigener Problemlösung für nachhaltiges Wissen.

Wann wählt man Rekursion in der Praxis?

Rekursion eignet sich für divide-and-conquer-Strategien wie QuickSort oder Fraktale, wo der Code kürzer und intuitiver ist. Mit Tail-Optimierung oder Memoization wird sie effizient. Iterative Umsetzungen bevorzugen sich bei hohem Speicherbedarf; Schüler üben dies durch Fallstudien und bewerten Algorithmen anhand von Big-O-Notation.