Iterativ und rekursiv – Übung
Du hast die Rekursion in C zwar theoretisch verstanden, weißt aber noch nicht genau, wie man sie praktisch anwenden kann? Im folgenden Beitrag zeigen wir dir die Rekursion an einem einfachen Beispiel.
Inhaltsübersicht
Übung zur Iteration und Rekursion
Das beliebteste und auch am besten darzustellende Problem, das man oft rekursiv löst, sind die Türme von Hanoi. Dabei handelt es sich aber nicht etwa um richtige Türme, sondern um ein Spiel. Zur Vorbereitung werden drei Stäbe in die Erde gesteckt. Dann nehmen wir einfache Holzscheiben und stecken sie auf einen der Stäbe.
Die größte Scheibe kommt nach unten, dann stapeln wir die nächst kleinere darauf, bis wir bei der kleinsten angekommen sind. Die Mindestmenge an Scheiben für dieses Spiel ist drei, wir können aber auch bis zu 5 Scheiben dazu nehmen, um den Schwierigkeitsgrad zu steigern, und das tun wir auch.
Die Türme von Hanoi: Spielregeln
Aber was ist jetzt das Ziel dieses Spiels? Tatsächlich sollen hier der oder die Spieler einfach dafür sorgen, dass alle Scheiben in der selben Reihenfolge, wie sie jetzt auf unserem ganz linken Stapel liegen, auf unserem ganz rechten Stab stecken. Da das so noch zu einfach wäre, gelten noch einige Regeln. Zum einen darf immer nur eine Scheibe, und zwar die oberste eines jeden Turmes abgehoben werden, zum anderen darfst du nie eine größere auf eine kleinere Scheibe legen.
Rekursive Lösung des Spiels – Drei Schritte
Um das Ganze jetzt rekursiv zu lösen, benennen wir zunächst unsere Stapel: Der erste ist der Source-Stapel, der zweite der help-Stapel und der dritte ist der goal-Stapel. Jetzt müssen wir uns aber wirklich Gedanken machen, wie wir das Problem konkret lösen.
Hast du schon eine Idee? Hier ist ein kleiner Tipp: Wir brauchen drei Schritte, um dieses Problem zu lösen. Der erste sorgt dafür, dass, wenn unser Turm aus mehr als einer Scheibe besteht, die oberen Scheiben zur Zielposition transportiert werden. Genauer definiert bedeutet das, dass, wenn unser Turm n>1 Scheiben aufweist, der obere Turm bestehend aus n-1 Scheiben nach help bewegt wird.
Der zweite Schritt ist dann, die verbleibende Scheibe von source nach goal zu transportieren. Schritt 3 wird ausgeführt, wenn ein Turm aus n>1, also mehr als einer Scheibe besteht. Tritt das ein, so schaffen wir den aus n-1 Scheiben bestehenden Turm nach goal.
In Programmcode sieht das Ganze dann so aus:
Lassen wir das jetzt durchlaufen, erhalten wir genau die Anweisungen, die wir zur Lösung unseres Problems brauchen.
Ausführung der Schritte
Aber wie funktioniert das jetzt? Unsere Main-Methode ist hier unsere erste Station. Hier rufen wir unsere move_disk Funktion auf und definieren deren Start-Parameter. Der Einfachheit halber nehmen wir dazu char Variablen, weswegen unser source-Turm nun zu s wird, der help-Stapel zu h und der goal-Stapel zu g.
In der Funktion move_disk selbst passiert allerdings die eigentliche Magie. Zunächst einmal haben wir eine Fallunterscheidung, bei der geprüft wird, wie viele Scheiben auf Stapel a liegen. Liegt dort nur eine, so legen wir sie einfach direkt auf Stapel c. Beim ersten Durchlauf ist Stapel a der Source-Stapel, weshalb n definitiv nicht eins ist. Wir springen also in den else-Block und führen die dortigen Anweisungen aus. Bei diesen handelt es sich um rekursive Aufrufe. Als Erstes rufen wir, wie wir bereits in Schritt eins festgelegt haben, dieselbe Funktion für n-1 nochmal auf. Haben wir das hinter uns, können wir mit dem nächsten Aufruf weitermachen. Dieser macht dasselbe, vertauscht aber unsere Türme, damit wir alles, was wir nach b gestapelt haben weiter nach h stapeln können. Als Letztes bewegen wir jetzt alles nach g.
Du hast jetzt ein kompliziertes Problem mit sehr wenig Code gelöst. Wenn du immer noch nicht genug hast, kannst du ja mit einigen Werten experimentieren.