Doppelstunde 9: Rekursive Algorithmen

Das Thema „Rekursion“ kommt im Bildungsplan auch in anderen Zusammenhängen vor:

• 3.2.2.2 „Algorithmen auf Datenstrukturen“
  • (6) ein höheres vergleichsbasiertes rekursives Sortierverfahren (zum Beispiel Mergesort, Quicksort) beschreiben [LF: händisch durchführen und eines davon implementieren]
• 3.2.2.3 „Rekursion“
  • (1) zu geeigneten Problemstellungen (zum Beispiel Türme von Hanoi, Baumtraversierung) rekursive Algorithmen unter Angabe von Rekursionsschritt und Rekursionsbasis entwerfen und von Hand durchführen
  • (2) das Divide-and-Conquer-Prinzip an geeigneten Problemstellungen erläutern
  • (3) rekursive Algorithmen zu unterschiedlichen Problemstellungen (zum Beispiel Fakultätsfunktion, Fibonacci-Zahlen, Kochsche Schneeflocke) implementieren
  • (4) LF: Rekursionsabläufe darstellen (unter anderem am call stack, Baum)
  • (5) LF: iterative Algorithmen und rekursive Algorithmen zur Lösung derselben Problemstellung vergleichen (unter anderem hinsichtlich Laufzeit) und bewerten

Wie genau sich die Schülerinnen und Schüler mit dem Thema auskennen, hängt also von der unterrichteten Reihenfolge und Intensität ab. In dieser Stunde wird auf die Punkte 3.2.2.3 (1) und (4) eingegangen.

Als Ausgangsproblem wird das Spiel „Türme von Hanoi“ verwendet, das bereits in Doppelstunde 5 als Anwendung von Stacks implementiert wurde. Die Frage hierbei ist, wie der Computer das Problem lösen könnte. Die Präsentation 11_rekursion.odp illustriert die Vorgehensweise. Die grundlegende Überlegung ist: „Ich weiß nicht, wie ich n Scheiben umschichten kann. Ich weiß nur, wie man eine Scheibe verschiebt. Aber mein Nachbar weiß, wie man n-1 Scheiben umschichtet. Wenn dieser n-1 Scheiben auf den Hilfsstapel gelegt hat, kann ich die unterste Scheibe auf den Zielstapel schieben, dann kann mein Nachbar die n-1 Scheiben vom Hilfsstapel auf den Zielstapel umschichten.“

Es bietet sich an, diese Vorgehensweise im Rollenspiel mit einem echten Hanoi-Spiel auszuführen. Dabei kann man mit kleinen Problemen (3 Scheiben) beginnen und sich bis zu 5 Scheiben steigern (danach wird es langwierig, da man für n Scheiben 2ⁿ-1 Züge benötigt). Die Schülerinnen und Schüler, die teilnehmen, werden dazu in einer Reihe hingesetzt und Sie beginnen mit der Aufgabe, 3 Scheiben umzuschichten. Da Sie das selbst nicht können, geben Sie es an die nächste Person weiter mit dem Auftrag, zwei Scheiben umzuschichten usw. Wichtig ist, die Kursmitglieder daran zu erinnern, dass „niemand weiß“, wie man mehr als eine Scheibe verschiebt, sondern alle den Gedanken umsetzen „ich lasse meinen Nachbarn das kleinere Problem lösen“.

Danach wird untersucht, wie dieses Prinzip am Computer ausgeführt wird. Eine Pseudocode-Notation beschreibt den Ablauf des Programms.

verschiebe(n,ursp,ziel,hilf):
  falls n = 1:
    bewege(ursp,ziel)
  sonst:
    verschiebe(n-1,ursp,hilf,ziel)
    bewege(ursp,ziel)
    verschiebe(n-1,hilf,ziel,ursp)

Um das Verständnis des Ablaufs zu verbessern ersetzt man zur ersten Näherung jeden rekursiven Aufruf schrittweise durch den Teil des Funktionsrumpfs, der tatsächlich durchlaufen wird (d.h. ein Zweig der Fallunterscheidung):

Dieser Ablauf lässt sich auch grafisch darstellen. Die Präsentation zeigt auf Folie 8, wie die Rekursion als Baum dargestellt werden kann. Jeder Funktionsaufruf steht für einen Knoten, ein rekursiver Aufruf führt zu seinen Kindknoten. Bei der Ausführung der Funktion wird im Fall von des Hanoi-Problems eine Inorder-Traversierung des Rekursionsbaums durchgeführt.

Zuletzt wird noch erörtert, was auf technischer Ebene in einem Von-Neumann-Rechner geschieht. Jeder Funktionsaufruf (auch nicht-rekursive) führt dazu, dass ein Stack-Frame im Stack-Segment des Arbeitsspeichers abgelegt wird, das die Rücksprungadresse und ggf. Parameter und lokale Variablen enthält. Die Präsentation zeigt, wie sich ein solcher Stack-Frame im Laufe der Lösung des Hanoi-Spiels verändert.

In einer anschließenden Übungsphase sollen die Schülerinnen und Schüler mit dem Aufgabenblatt 11_rekursion_manuell.odt zunächst manuell den Rekursionsablauf an zwei einfachen Beispielen darstellen: Auf Papier soll zum einen ein Rekursionsbaum gezeichnet werden, der den Ablauf der Fibonacci-Funktion darstellt. Zum anderen soll der Stack simuliert werden, der bei der rekursiven Berechnung der Potenzfunktion mittels „square and multiply“ entsteht. Dieser zweite Schritt kann gerne in Partnerarbeit behandelt werden. Dazu erhalten die Schülerinnen und Schüler Karten
(11_rekursion_manuell_kaertchen.odt), die einen Funktionsaufruf repräsentieren. Zuunterst soll das erste Kärtchen auf den Tisch gelegt werden, das bereits die Parameter 2 und 11 eingetragen hat. Aufgabe der Schülerinnen und Schüler ist, den Pseudocode durchzugehen und die lokalen Variablen bei Bedarf zu aktualisieren. Bei einem rekursiven Aufruf werden die lokalen Variablen auf dem Kärtchen notiert und ein neues Kärtchen mit den entsprechenden Parametern auf den Stapel gelegt. Wenn eine Funktion vollständig durchlaufen wurde (bis zum return-Statement), wird der Rückgabewert auf dem Kärtchen notiert und das Kärtchen wird vom Stapel genommen. Das Ergebnis überträgt man auf das darunterliegende Kärtchen (in die Variable b). Auf diese Weise wird der vollständige Ablauf der Funktion simuliert, bis man zum Endergebnis kommt.

Zum Abschluss (oder optional als Differenzierung) wird der Hanoi-Algorithmus implementiert. Das Aufgabenblatt 11_hanoi_automatisch.odt beschreibt, was zu tun ist. In das Ergebnis aus Doppelstunde wird eine weitere Methode loese() eingebaut, die das automatische Lösen implementiert. Sollten einzelne Kursmitglieder die Implementation nicht geschafft haben, können Sie ihnen die Musterlösung zur Verfügung stellen. Wenn man in BlueJ ein Objekt vom Typ HanoiGame erzeugt, erscheint es unten in der Objektliste. Damit kann man die Methode loese() aufrufen lassen.

Unterrichtsverlauf: Herunterladen [odt][187 KB]

Weiter zu DS 10: Tiefen- und Breitensuche