Skip to main content

Exkurs: Rekursive Funktionen

In diesem Artikel behandeln wir eine Technik, genannt Rekursion, die viele Studierende am Anfang etwas ungewohnt und schwierig finden. Rekursion ist eines dieser Konzepte, die man nach einer gewissen Gewöhnungszeit als ganz natürlich erachtet, und dann nicht mehr verstehen kann, was denn eigentlich am Anfang schwierig zu verstehen war. In der Tat müssen wir um Rekursion einzuführen gar kein neues Programmierkonzept lernen. Rekursion ist nämlich einfach die Möglichkeit von Funktionen, nicht nur andere Funktionen aufzurufen, sondern auch sich selbst.

Da wir für die tägliche Programmierung gut ohne den Einsatz von Rekursion aus ist dieses Konzept für uns nicht prüfungsrelevant. Trotzdem empfehlen wir Ihnen, sich das folgende Video anzuschauen, da Rekursion ein sehr schönes Konzept ist, dem sie vielleicht auch später in einer Mathematikvorlesung oder weiterführenden Programmierkursen wieder begegnen werden.

Das Grundprinzip​

Das klassische Beispiel um Rekursion einzuführen ist die Berechnung der Fakultätsfunktion. Wir erinnern uns, dass die Fakultätsfunktion wie folgt definiert ist:

n!=n⋅(n−1)⋅(n−2)⋅…,⋅2⋅1.n! = n \cdot (n - 1) \cdot (n - 2) \cdot \ldots, \cdot 2 \cdot 1.

Als Beispiel ist 5!=5⋅4⋅3⋅2⋅1=1205!= 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120.

Diese Funktion kann rekursiv wie folgt definiert werden:

n!=n⋅(n−1)!0!=1\begin{array}{l} n! = n \cdot (n - 1)! \\ 0! = 1 \end{array}

Das Prinzip dabei ist, dass die Funktion durch sich selbst definiert ist. So ist 3!=3⋅(2)!=3⋅2⋅1!=3⋅2⋅03! = 3 \cdot (2)! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 0. Die Rekursion endet, wenn der Spezialfall 0!0! erreicht wird.

Im nachfolgenden Video diskutieren wir, wie wir dies in Python umsetzten können.

Hier können Sie das Gelernte gleich wieder in der Praxis anwenden.

Rekursive Grafiken: Das Sierpinski Dreieck​

Wir können Rekursion auch zusammen mit Turtlegrafik nutzen, um Zeichnungen zu erstellen, bei welchen das Muster selbst jeweils wieder Teil des Musters ist. Es gibt dafür viele schöne Beispiele. Das bekannteste ist wahrscheinlich das Sierpinski Dreieck, welches Sie im folgenden Code finden.

Wenn Sie sich den Code anschauen sehen sie, dass eine Zeichnung aus jeweils drei rekursiven Aufrufen besteht, in denen jeweils wieder dasselbe Muster gezeichnet wird. Die Rekursion bricht ab, wenn die Rekursionstiefe (angegeben durch die Variable depth) den Wert 0 erreicht hat. In diesem Fall wird ein einfaches Dreieck gezeichnet.

Experimente​

  • Verschieben Sie die Startposition so, dass die ganze Figur gut zu sehen ist.
  • Rufen Sie die Methode zu Beginn mit unterschiedlichen Tiefen auf (z.B. 1 oder 4).

Fragen und Kommentare​

Haben Sie Fragen oder Kommentare zu diesem Artikel? Nutzen Sie das Forum und helfen Sie sich und Ihren Mitstudierenden dieses Thema besser zu verstehen.