Informatik · Klasse 11 · Algorithmen und Komplexität · 2. Halbjahr

Rekursion und Iteration

Vergleich von rekursiven und iterativen Lösungsansätzen für Probleme.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen entwerfen
• KMK: Sekundarstufe II - Strukturieren

Über dieses Thema

Rekursion und Iteration sind zentrale Ansätze zur Lösung algorithmischer Probleme in der Oberstufe. Schüler vergleichen rekursive Funktionen, die sich selbst mit verkleinerten Problemen aufrufen, mit iterativen Schleifen, die Zustände wiederholt aktualisieren. Sie analysieren Beispiele wie die Fibonacci-Folge oder das Hanoi-Türmchen: Rekursion ermöglicht elegante Darstellungen für fraktale oder baumartige Strukturen, verbraucht jedoch mehr Stapelspeicher und kann bei tiefer Rekursion zu Überläufen führen. Iteration ist speichereffizienter und schneller, wirkt aber bei komplexen Hierarchien oft komplizierter.

Im KMK-Lehrplan Sekundarstufe II steht das Entwerfen und Strukturieren von Algorithmen im Vordergrund. Schüler lernen, rekursive in iterative Varianten umzuwandeln, indem sie Aufrufstapel durch Schleifen und Akkumulatoren ersetzen. Dies schult Komplexitätsbewertung in Zeit und Raum und verbindet mit Themen wie Divide-and-Conquer-Strategien. Solche Vergleiche fördern tiefes Verständnis für Algorithmendesign.

Aktives Lernen passt ideal, weil Schüler Konzepte durch Coding, Visualisierungen und Peer-Diskussionen erproben. Pair-Programming oder Gruppensimulationen machen Stapelaufbau sichtbar, erleichtern den Vergleich und festigen die Fähigkeit, Lösungen bewusst zu wählen.

Leitfragen

1. Vergleichen Sie die Vor- und Nachteile von rekursiven und iterativen Algorithmen.
2. Analysieren Sie, welche Probleme sich besonders gut für eine rekursive Lösung eignen.
3. Erklären Sie, wie man eine rekursive Funktion in eine iterative umwandeln kann.

Lernziele

• Vergleichen Sie die Laufzeit- und Speicherkomplexität von rekursiven und iterativen Implementierungen für gegebene Probleme (z. B. Fakultät, Fibonacci).
• Analysieren Sie die Eignung von rekursiven Algorithmen für Probleme mit hierarchischer oder baumartiger Struktur (z. B. Traversierung von Bäumen).
• Erklären Sie die Funktionsweise des Aufrufstapels (Call Stack) bei der Ausführung von rekursiven Funktionen und wie dieser zu Stack-Overflow-Fehlern führen kann.
• Entwerfen Sie eine iterative Lösung für ein Problem, das ursprünglich rekursiv formuliert wurde, indem Sie explizite Datenstrukturen (z. B. Stacks) verwenden.

Bevor es losgeht

Grundlagen von Funktionen und Funktionsaufrufen

Warum: Schüler müssen verstehen, wie Funktionen aufgerufen werden und wie Parameter übergeben werden, um die Funktionsweise von Rekursion zu begreifen.

Kontrollstrukturen (Schleifen: for, while)

Warum: Ein tiefes Verständnis von Schleifen ist notwendig, um iterative Lösungen zu entwickeln und sie mit rekursiven Ansätzen vergleichen zu können.

Grundlegende Datenstrukturen (Arrays, Listen)

Warum: Für die Umwandlung von Rekursion in Iteration werden oft explizite Datenstrukturen wie Stacks benötigt, deren grundlegende Handhabung bekannt sein muss.

Schlüsselvokabular

Rekursion	Ein Lösungsansatz, bei dem eine Funktion sich selbst aufruft, um kleinere Teilprobleme zu lösen, bis ein Basisfall erreicht ist.
Iteration	Ein Lösungsansatz, der eine Folge von Operationen wiederholt ausführt, typischerweise mithilfe von Schleifen (for, while), bis eine Abbruchbedingung erfüllt ist.
Aufrufstapel (Call Stack)	Eine Datenstruktur, die Informationen über aktive Unterprogrammaufrufe speichert. Bei Rekursion speichert sie die Zustände der einzelnen Funktionsaufrufe.
Basisfall	Die Bedingung in einer rekursiven Funktion, die den rekursiven Aufruf beendet und eine direkte Rückgabe ermöglicht, um eine Endlosschleife zu verhindern.
Stapelüberlauf (Stack Overflow)	Ein Fehler, der auftritt, wenn der Aufrufstapel zu groß wird, weil zu viele rekursive Aufrufe ohne Erreichen des Basisfalls erfolgen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Rekursion ist immer langsamer als Iteration.

Was Sie stattdessen lehren sollten

Rekursion kann bei Tail-Optimierung ebenso effizient sein, Iteration spart meist Speicher. In Pair-Programming vergleichen Schüler Messungen und entdecken, dass Effizienz vom Problem abhängt, was nuanciertes Denken fördert.

Häufige Fehlvorstellung

Jede rekursive Funktion läuft unendlich.

Was Sie stattdessen lehren sollten

Ohne Basisfall ja, doch korrekte Rekursion terminiert. Gruppensimulationen des Aufrufbaums zeigen, wie Basisfälle die Tiefe begrenzen, und helfen Schülern, Fehler früh zu erkennen.

Häufige Fehlvorstellung

Alle Probleme lassen sich nur iterativ lösen.

Was Sie stattdessen lehren sollten

Rekursion eignet sich natürlich für rekursive Strukturen wie Bäume. Diskussionen in kleinen Gruppen verdeutlichen, wann Eleganz Vorrang hat, und stärken Problemlösekompetenz.

Ideen für aktives Lernen

Pair Programming: Fibonacci-Vergleich

Paare coden rekursive und iterative Fibonacci-Funktionen in Python oder Java. Sie messen Laufzeiten mit timeit für n=30 bis 40 und notieren Stapelverbrauch. Abschließend teilen sie Erkenntnisse in der Klasse.

35 Min.·Partnerarbeit

Small Groups: Hanoi-Simulation mit Karten

Gruppen bauen Hanoi-Türmchen mit Stapeln von Karten nach und protokollieren Züge rekursiv und iterativ. Sie zeichnen den Rekursionsbaum und diskutieren Minimierung von Schritten. Präsentation der Modelle folgt.

45 Min.·Kleingruppen

Whole Class: Umwandlungs-Challenge

Die Klasse diskutiert eine rekursive Funktion, z. B. für Binärsuchbaum-Traversierung. Gemeinsam wandeln sie sie iterativ um, indem sie Stapel simulieren. Jeder notiert Vor-/Nachteile.

30 Min.·Ganze Klasse

Individual: Code-Analyse

Jeder Schüler erhält rekursiven Code, transformiert ihn iterativ und testet mit Unit-Tests. Ergebnisse werden in einem Portfolio abgelegt.

25 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• In der Softwareentwicklung werden rekursive Algorithmen häufig für die Verarbeitung von Baumstrukturen wie Dateisystemen oder XML-Dokumenten verwendet. Ein Systemadministrator könnte beispielsweise rekursiv Verzeichnisse durchsuchen, um alle Dateien eines bestimmten Typs zu finden.
• Grafikdesigner und Spieleentwickler nutzen Rekursion zur Erzeugung von fraktalen Mustern, wie sie in der Natur vorkommen (z. B. Küstenlinien, Bäume). Ein Algorithmus zur Generierung von Landschaften in einem Computerspiel könnte rekursiv Terrassen oder Berge erstellen.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Zeigen Sie den Schülern zwei Code-Snippets: eine rekursive und eine iterative Implementierung zur Berechnung der Fakultät. Bitten Sie sie, auf einem Arbeitsblatt zu notieren, welches Snippet sie für speichereffizienter halten und warum. Sammeln Sie die Arbeitsblätter zur schnellen Überprüfung des Verständnisses.

Diskussionsfrage

Stellen Sie die Frage: 'Unter welchen Umständen würden Sie als angehender Softwareentwickler eine rekursive Lösung einer iterativen vorziehen, auch wenn sie potenziell mehr Speicher benötigt?' Leiten Sie eine kurze Klassendiskussion, bei der Schüler die Vor- und Nachteile abwägen und Beispiele nennen.

Lernstandskontrolle

Geben Sie jedem Schüler eine Karte mit einer Problembeschreibung (z. B. 'Durchsuche eine verschachtelte Ordnerstruktur nach einer bestimmten Datei'). Bitten Sie die Schüler, kurz zu beschreiben, ob eine rekursive oder iterative Herangehensweise hierfür besser geeignet ist und begründen Sie ihre Wahl mit einem Satz.

Häufig gestellte Fragen

Wie vergleiche ich Vor- und Nachteile von Rekursion und Iteration?

Rekursion bietet intuitive Lösungen für hierarchische Probleme wie Bäume oder Fraktale, ist aber anfällig für Stapelüberlauf und höheren Speicherverbrauch. Iteration vermeidet Rekursionstiefe durch Schleifen, ist speichersparender und oft schneller, wirkt bei komplexen Fällen jedoch umständlicher. Schüler messen Laufzeiten und Stapelgrößen, um konkrete Unterschiede zu quantifizieren. Dies schult Komplexitätsanalyse nach Big-O.

Welche Probleme eignen sich besonders für rekursive Lösungen?

Probleme mit natürlicher Selbstähnlichkeit wie Fibonacci, Hanoi-Türmchen, Traversierungen von Bäumen oder Backtracking in Spielen. Hier zerlegt Rekursion das Problem in kleinere Instanzen. Iterative Alternativen erfordern oft explizite Stapelsimulation. Schüler identifizieren Kandidaten durch Analyse der Problemmodelle und wählen basierend auf Kontext.

Wie wandelt man eine rekursive Funktion iterativ um?

Ersetzen Sie Rekursionsaufrufe durch eine Schleife mit Stapel oder Akkumulatoren: Speichern Sie Parameter auf einem Stack, verarbeiten Basisfälle zuerst. Bei Tail-Rekursion reicht ein Loop mit Update. Beispiel Fibonacci: Iterativ mit zwei Variablen für Vorgängerwerte. Testen mit Einheiten-Tests sichert Korrektheit und vergleicht Effizienz.

Wie hilft aktives Lernen beim Verständnis von Rekursion und Iteration?

Aktives Lernen macht abstrakte Konzepte konkret: Durch Pair-Programming implementieren Schüler beide Varianten, messen Zeiten und visualisieren Stapel. Gruppensimulationen wie Hanoi mit physischen Modellen zeigen Aufrufdynamik. Klassen-Diskussionen fördern Vergleiche und Fehlkorrektur. Solche Methoden steigern Retention um 50 Prozent, da Schüler aktiv experimentieren und peer feedback erhalten.