Die Rekursion ist eine grundlegende Technik in der Informatik, die die Methode beschreibt, dass eine programmierte Funktion sich selbst aufrufen kann und dadurch das Problem schrittweise in kleinere Teilprobleme auflöst, welche einfacher zu lösen sind. Dies wird dann beispielsweise Sortieralgorithmen oder beim Durchlaufen von Baumstrukturen genutzt. 

In diesem Beitrag schauen wir uns die Struktur von Rekursionen genauer an und verstehen diese Methode mithilfe von einfachen Beispielen in der Programmiersprache Python. Außerdem zeigen wir die Vor- und Nachteile dieser Technik und stellen die Unterschiede zu normalen Iterationen heraus. Zum Verständnis des Artikels sollte ein grundlegendes Wissen der Programmiersprache Python vorhanden sein, um den Beispielen folgen zu können.. 

Was ist eine Rekursion?

Die Rekursion ist ein Konzept aus der Informatik, welches sich dadurch auszeichnet, dass eine Funktion sich selbst aufruft. Der Sinn dahinter liegt darin, dass die Funktion das übergeordnete Problem in einfachere Teilprobleme aufsplittet und dadurch schrittweise zur Lösung gelangt. Diese Abfolge wiederholt sich so lange bis der sogenannte Basisfall erreicht ist und die Rekursion gestoppt wird. 

Ein klassisches Beispiel für die Rekursion ist die Berechnung der Fakultät \(n!\) einer Zahl \(n\). Diese ist so definiert, dass die Fakultät einer Zahl \(n\) einfach das Produkt aus der Zahl selbst mit der Fakultät der nächstkleineren Ganzzahl \(n-1\) ist. Mathematisch ausgedrückt befolgt die Fakultät also die folgende Formel: 

\(\) \[ n!=n\times\left(n-1\right)!\]

Bei dieser Formel wird bereits der rekursive Ansatz der Fakultät deutlich, indem für eine große Zahl diese einfach berechnet werden kann bis der Basisfall \(1!\) erreicht ist. 

Im Allgemeinen unterscheidet man zwei Arten von Rekursionen: 

• Die Direkte Rekursion beschreibt den Fall, dass eine Funktion sich direkt selbst aufruft. Dies ist mit Abstand der häufigere Fall in der Informatik. In dem folgenden Beispiel ruft die Funktion f() sich innerhalb des Funktionsablaufs selbst auf, bis eine Abbruchbedingung erreicht ist. 

• Bei der Indirekten Rekursion erfolgt der Aufruf von f() nicht direkt über die Funktion selbst, sondern über eine zweite Funktion, wie beispielsweise g(). Dadurch entsteht eine Kette in der die Funktion f() erst g() aufruft, woraufhin g() dann wiederum f() aufruft. Die Indirekte Rekursion ist deutlich komplexer, da mehr Funktionen am Ablauf beteiligt sind, jedoch folgt sie trotzdem dem Prinzip der schrittweisen Problemlösung. 

Die Rekursion ist eine mächtige Technik innerhalb der Informatik, um komplexe Probleme in einfachere und lösbare Teilprobleme aufzusplitten. 

Wie ist die Struktur von Rekursionsfunktionen?

Die Rekursion besteht aus zwei grundlegenden Komponenten, dem Basisfall und dem rekursiven Fall. Diese sorgen dafür, dass die Funktion das Problem so lange in Teilprobleme aufsplittet, bis eine endgültige Lösung gefunden wurde. 

Basisfall (Abbruchbedingung)

Der Basisfall, oder auch Abbruchbedingung genannt, ist die Bedingung, die dazu führt, dass der Algorithmus beendet und eine Lösung ausgegeben wird. Ohne die Abbruchbedingung würde die Schleife endlos laufen und in einen Fehler laufen, sobald der Speicher für Funktionsaufrufe überläuft. Der Basisfall ist der einfachste Fall des Problems, bei dem keine weiteren rekursiven Aufrufe nötig sind. 

Bei der Berechnung der Fakultät beispielsweise ist der Basisfall erreicht, wenn n == 0 und keine weitere Rekursion notwendig ist: 

Rekursiver Fall

Der rekursive Fall ist der Teil der Funktion, in dem sie sich weiterhin selbst aufruft und das Problem in kleinere Teilprobleme zerlegt. Hierbei muss sichergestellt werden, dass der rekursive Fall dafür sorgt, dass sich die Funktion schrittweise dem Basisfall annähert und sich nicht davon entfernt. Dies zeigt sich dadurch, dass in jedem Schritt das verbleibende Problem kleiner wird. 

Bei der Fakultätsberechnung wird die Zahl im rekursiven Fall in jedem Schritt um 1 kleiner, bis sie schließlich 0 erreicht: 

Die Rekursion setzt sich schließlich aus diesem Zusammenspiel des rekursiven Falls und des Basisfalls zusammen, welches dafür sorgt, dass das Gesamtproblem schrittweise kleiner und schlussendlich dann gelöst wird.

Was sind klassische Beispiele für rekursive Funktionen?

Um die Funktionalität der Rekursion genauer zu verstehen, wollen wir uns in diesem Abschnitt zwei klassische Beispiele mit konkreten Werten genauer ansehen. Diese illustrieren, wie kleinere Teilprobleme gebildet und schrittweise gelöst werden. 

Berechnung der Fakultät

Die Berechnung der Fakultät ist mathematisch definiert als das Produkt aller positiven Ganzzahlen bis zur Zahl selbst, also: 

\(\) \[ n!=n\times\left(n-1\right)\times\left(n-2\right)\times\ldots\times1 \]

Die rekursive Funktion dafür in Python haben wir bereits vorgestellt. Sie besteht aus dem Basisfall und dem rekursiven Fall. 

Nun wollen wir uns die einzelnen Schritte genauer ansehen, um die Fakultät von 4 zu berechnen. Die einzelnen Schritte dazu sehen wie folgt aus: 

• Bei factorial(4) ruft die Funktion zuerst die Funktion für factorial(3) auf. 
• Mit factorial(3) wird wiederum factorial(2) aufgerufen und entsprechend factorial(1). 
• Dies passiert so lange bis der Basisfall factorial(0) erreicht ist, welcher wiederum 0 zurückgibt. Hier sind die einzelnen Ergebnisse der Teilprobleme, welche nun multipliziert werden: 
  • factorial(1) gibt 1 zurück. 
  • factorial(2) gibt 2 * 1 = 2 zurück.
  • factorial(3) gibt 3 * 2 = 6 zurück. 
  • Schlussendlich gibt factorial(4) 4 * 6 = 24 zurück, was das endgültige Ergebnis ist. 

Fibonacci-Folge

Die Fibonacci-Folge ist ein weiteres mathematisches Problem, welches häufig mithilfe einer Rekursion gelöst wird. Hierbei handelt es sich um eine Folge, bei der ein beliebiges Element aus der Summe der beiden vorangegangenen Elemente berechnet wird:

\(\) \[ F(n)\ =\ F(n-1)\ +\ F(n-2) \]

Diese Folge beginnt mit den Werten für 0 und 1 für die wiederum gilt: 

\(\) \[ F(0)\ =\ 0;\ F(1)\ =\ 1\]

In Python kann diese rekursive Folge mithilfe der folgenden Funktion berechnet werden: 

Die Funktion zeichnet sich dadurch aus, dass zwei Basisfälle definiert sind, nämlich einmal für n==0 und einmal für n==1. 

Für fibonacci(5) ergibt sich dann der folgende Ablauf: 

• Zum Start werden fibonacci(4) und fibonacci(3) berechnet. 
• Diese Aufrufe wiederholen sich, bis die Basisfälle erreicht werden. 
• Zum Abschluss werden die einzelnen Ergebnisse aufsummiert und das Endresultat fibonacci(5) = 4 + 3 + 2 + 1 + 0 = 10 ausgegeben. 

Anwendungsbeispiele in der Praxis

Neben diesen mathematischen Problemen gibt es auch einige andere Anwendungsbeispiele in der Praxis in denen die Rekursion verwendet wird:

• Sortieralgorithmen: Bei der Sortierung von Elementen, wie beispielsweise Python Listen, kommen Sortieralgorithmen, wie Merge Sort oder Quick Sort zum Einsatz. Diese teilen die Listen in kleinere Elemente und sortieren diese unabhängig voneinander. Abschließend werden diese dann wieder zusammengeführt.  
• Suchalgorithmen: Bei der Suche von einzelnen Elementen in einer großen Datenstruktur wird die Suche in rekursive Fälle eingeteilt, indem die Datenstruktur schrittweise halbiert wird und dann die kleineren Teile durchsucht werden.
• Baumtraversierung: In verschiedenen Dateisystemen, wie zum Beispiel beim XML-Parsing, wird die Rekursion angewendet, um die hierarchischen Strukturen zu durchlaufen und dadurch alle Punkte des Baumes zu durchlaufen. 
• Fraktale: Die Rekursion wird außerdem bei der Erstellung von sogenannten Fraktalen verwendet. Dabei handelt es sich um geometrische Muster, welche sich auf unterschiedlichen Ebenen von Vergrößerungen wiederholen. 

Die Rekursion ist ein vielseitiges Konzept, welches in einer breiten Menge von Problemen genutzt wird. 

Was ist der Unterschied zwischen einer Rekursion und Iteration?

In der Programmierung sind die Rekursion und die Iteration zwei grundlegende Ansätze, um wiederholte Berechnungen umzusetzen. Obwohl beide Methoden zum selben Ergebnis führen, unterscheiden sie sich grundlegend in der Herangehensweise, wodurch die Wahl große Auswirkungen auf die Effizienz des Algorithmus hat. 

Eine rekursive Funktion ruft sich selbst auf, um das Problem in Teilprobleme aufzulösen und diese schrittweise zu lösen. Bei einer Iteration hingegen werden Schleifen, wie in Python beispielsweise for oder while, verwendet, um bestimmte Codeblöcke wiederholt auszuführen. 

In den folgenden Abschnitten werden wir diese beiden Herangehensweisen basierend auf verschiedenen Parametern vergleichen: 

• Eleganz und Lesbarkeit: In vielen Fällen bietet die Rekursion einen deutlich einfacheren und besser lesbaren Code, da sie sich an die natürliche Struktur des Problems anpassen. Bei einfacheren Problemen hingegen kann die Iteration klarer erscheinen, zum Beispiel beim Durchlaufen von Datenstrukturen, wie NumPy Arrays oder Pandas DataFrames.
• Speicher: Bei der Rekursion erzeugt jeder Funktionsaufruf einen gewissen Overhead und wird in dem sogenannten Call-Stack hinterlegt. In komplexen Fällen kann es deshalb zu einem sogenannten Stack-Overflow Fehler kommen, der das Programm zum Abbruch zwingt. Die Iteration hingegen ist häufig effizienter, da sie direkt auf die Datenstrukturen zugreifen kann und kein zusätzlicher Overhead erzeugt wird. 
• Performance: Durch die Speicherproblematik kann die Rekursion ineffizienter sein als die Iteration, da das Speichern und Wiederherstellen von Kontexten Zeit benötigen und Speicher binden. 

Die Rekursion ist vor allem dann gut geeignet, wenn sich das Problem selbst schon rekursiv formulieren lässt und bietet dafür eine einfache und natürliche Lösung. Die Iteration hingegen sollte verwendet werden, wenn die Anzahl der Iterationen bereits absehbar ist und der Zustand einfach verwaltet werden kann. 

Was sind die Vor- und Nachteile der Rekursion?

Bis zu diesem Punkt des Beitrags hat sich die Rekursion als sehr elegante Lösung herausgestellt, um komplexe Problematiken auf einfache und effiziente Weise zu lösen. Dabei sind sie außerdem einfacher zu implementieren und zu erwarten, da sie nicht so ausschweifend sind, wie eine iterative Lösung. Ohne die Rekursion müssten für solche Lösungen komplexe Schleifen gebildet werden, die unter Umständen zusätzliche Datenstrukturen erfordern würden. 

Außerdem bietet die Rekursion eine Anwendbarkeit in unterschiedlichsten Bereichen, wie beispielsweise bei mathematischen Problemen oder in der Informatik. Im vorherigen Abschnitt wurden bereits einige Probleme vorgestellt, die mithilfe der Rekursion gelöst werden können. Darüber hinaus gibt es viele Anwendungen, die von Grund auf bereits rekursiv sind, wie beispielsweise Baumstrukturen. 

Jedoch bringt die Rekursion auch einige Herausforderungen mit sich, die bei der Implementierung beachtet werden sollten: 

• Stack Overflow: Ein Stack Overflow Fehler tritt auf, wenn eine Schleife nicht endet und endlich lange weiterläuft bis der Speicher des Geräts überläuft. Bei Rekursionen kann dies passieren, wenn der Basisfall nicht sauber definiert ist und deshalb nie eintritt. Es muss deshalb sichergestellt werden, dass der Basisfall auch erreichbar ist. 
• Performance: Im Vergleich zu iterativen Ansätzen kann es bei der Rekursion zu Performanceproblemen kommen, da jeder Funktionsaufruf im sogenannten Call-Stack gespeichert wird und vor allem bei tiefen Rekursionen zu einem erhöhten Speicherverbrauch führt. Außerdem sind die Funktionsaufrufe mit einem Overhead verbunden, während iterative Ansätze direkt auf die Datenstrukturen zugreifen können.
• Tail Recursion: Eine spezielle Form der Rekursion ist die sogenannte Tail Recursion bei der der letzte Befehl einer Funktion ein rekursiver Aufruf ist. In einem solchen Fall kann der Compiler oder Interpreter den Speicherbedarf optimieren, indem er den Call-Stack nicht weiter befüllt. Dadurch wird Speicher gespart und die Performance optimiert. Jedoch unterstützen nicht alle Programmiersprachen ein solches Vorgehen. 

Insgesamt ist die Rekursion ein mächtiges Werkzeug, um komplexe Programmierprobleme zu lösen. Jedoch muss vor der Anwendung abgeschätzt werden, ob ein iterativer oder ein rekursiver Einsatz besser geeignet ist. 

Das solltest Du mitnehmen

• Die Rekursion ist ein Konzept aus der Informatik, bei der sich eine Funktion wiederholt selbst aufruft. 
• Dabei werden zwei grundlegende Komponenten unterschieden. Der Basisfall beschreibt die Bedingung, welche dazu führt, dass der Algorithmus endet. Der rekursive Fall hingegen führt zu einem erneuten Aufruf der Funktion. 
• Die Rekursion wird in verschiedensten mathematischen Problemen und in der Programmierung eingesetzt, wie zum Beispiel beim Sortieren von Elementen oder bei Suchalgorithmen. 
• Im Vergleich zur Iteration, also der Nutzung von Schleifen, hat die Rekursion einen größeren Overhead und kann deshalb Performanceprobleme aufweisen. Außerdem besteht die Gefahr eines Stack Overflows, welcher zum Abbruch des Programms führen kann. 

Andere Beiträge zum Thema Rekursion

Die Universität von Utah hat einen interessanten Artikel veröffentlicht, den Du hier finden kannst.