Iterativ und rekursiv
Du willst dich mit iterativen und rekursiven Funktionen etwas genauer beschäftigen? Im folgenden Beitrag erklären wir dir den Unterschied zwischen beiden Funktionen in C.
Inhaltsübersicht
Iterative und rekursive Funktion C
Iterative Funktionen kennst du bestimmt, wenn du dich bereits näher mit C beschäftigt hast. Dazu zählen beispielsweise die while- und die for-Schleife oder die if-Anweisung. Aber was sind jetzt diese rekursiven Algorithmen?
Rekursiv bedeutet in der Informatik, dass sich dein Algorithmus entweder über andere Funktionen oder direkt selbst aufruft. Deswegen unterteilen wir die Rekursion auch in zwei verschiedene Varianten: Die direkte und die indirekte Rekursion.
Direkte Rekursion C – Beispiel
Bei der direkten Rekursion wirst du irgendwo innerhalb deiner Funktion einen Aufruf von ihr finden. Um eine direkte Rekursion korrekt umsetzen zu können, kannst du dich an diesem Schema orientieren: Eine direkt rekursive Funktion braucht immer eine Eingabe, eine Abbruchbedingung und einen rekursiven Aufruf. Fehlt die Eingabe oder der rekursive Aufruf, handelt es sich um eine ganz andere Funktionsart, und arbeitet dementsprechend vielleicht nicht korrekt. Vergisst du aber die Abbruchbedingung, so bist du in einer endlosen Schleife gefangen.
Ein recht beliebtes Beispiel für die direkte Rekursion ist die Fakultätsberechnung, da man hier immer das Produkt für 
braucht, um n auszurechnen.
Wie du siehst, erhalten wir als Eingabe eine Zahl. Dann prüfen wir, ob diese Zahl Null ist. Das ist unsere Abbruchbedingung, denn von Null kann man keine Fakultät mehr berechnen. Als Nächstes widmen wir uns dem Aufruf, denn wir brauchen für unsere Rechnung ja schließlich noch . Ist unsere rekursive Kette abgeschlossen, geben wir zum Schluss noch unser Ergebnis aus.
Viele Studenten haben am Anfang Probleme, das Prinzip dahinter zu verstehen, da es recht abstrakt ist. Aber du kannst es dir ganz einfach so vorstellen, wie Klammern in der Mathematik. Du berechnest also praktisch 
auf diese Weise:
Dabei ist jede Klammer eine Rekursionsstufe beziehungsweise ein Funktionsaufruf.
Indirekte Rekursion und Vor -und Nachteile der Rekursion
Es gibt allerdings nicht nur die direkte Rekursion, sondern auch die indirekte. Deshalb schauen wir uns auch diese an: Für die indirekte Rekursion brauchen wir mindestens zwei Algorithmen, die sich in einem Zyklus gegenseitig aufrufen. Das heißt, dass z.B. Algorithmus A Algorithmus B aufruft und dieser wiederum A. Ansonsten bleibt das Prinzip aber identisch.
Aber was bringt dir die Rekursion jetzt? Es ginge doch auch alles mit iterativen Funktionen? Rekursive Implementierungen sind oft leichter zu realisieren als die iterative Alternative, außerdem sparst du dir meistens eine Menge Schreibarbeit. Allerdings haben sie auch einige Nachteile. Zum Beispiel den, dass sie sehr viel mehr Arbeitsspeicher verbrauchen und deswegen nicht sonderlich effizient sind. Deshalb kann durch zu große Rekursionstiefe auch ein Stack Overflow entstehen.
Jetzt weißt du, wie man mit rekursiven Algorithmen umgehen kann. Nun wollen wir uns die Rekursion noch an einem Beispiel anschauen.
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.
Beispiel: Die Türme von Hanoi
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.
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.