====== 1. Rekursion (Einführung) ====== ===== Beispiel 1: Berechnung von Fakultäten ===== Erinnern Sie sich noch an die Fakultätsfunktion? Sie ist so definiert: $$0! = 1$$ und $$n! = 1\cdot 2\cdot 3\cdot \ldots \cdot (n-1)\cdot n \ \mathrm{für}\ n \in \mathbb{N} \backslash \{0\},$$ also beispielsweise: $$5! = 1\cdot 2\cdot 3\cdot 4 \cdot 5 = 120$$ \\ * Probieren Sie das folgende Programm aus, auch im Einzelschrittmodus. * Analysieren Sie das Programm genau und überlegen Sie, welche Anweisungen der Reihe nach ausgeführt werden.
**Definition:** \\ Von **Rekursion** (von lateinisch //recurrere// == „zurücklaufen“) spricht man, wenn sich eine Methode entweder direkt selbst aufruft oder über eine Aufrufkette (z.B. Methode a ruft Methode b auf, die ruft Methode c auf, diese wiederum ruft Methode a auf). \\ \\ **Wichtig:** * Jede Rekursion benötigt eine **Abbruchbedingung**, die das Unterbrechen der Aufrufkette nach endlich vielen Schritten sicherstellt. * Ruft sich die rekursive Methode genau ein Mal auf, so spricht man von **linearer Rekursion**. Ruft sie sich mehrmals auf, so spricht man von **verzweigter Rekursion** (siehe Aufgabe 1 unten). === Erklärung des Programmablaufs: === **Was passiert mit den Werten der lokalen Variablen und Parameter beim rekursiven Methodenaufruf?** \\ Bei jedem Aufruf einer Methode reserviert der Computer Speicherplatz für alle Parameter und lokalen Variablen. Wird innerhalb der Methode erneut dieselbe Methode aufgerufen, so wird erneut "neuer" Speicher reserviert, diesmal an einer anderen Stelle. Der "alte" Speicher bleibt erhalten. Bei der Rückkehr mittels "return" wird der "neue" Speicher wieder freigegeben und der "alte" kommt wieder zum Einsatz. Bei jedem Betreten der Methode ''fakultät'' erhalten die Parameter und lokalen Variablen daher "neue" Werte, bei jedem Verlassen werden die "alten" Werte wiederhergestellt. \\ \\ {{ :rekursion:rekursion_erklaerung.png?direct&600 |}} Hier etwas gröber dargestellt: {{ :rekursion:rekursion.svg |}} ===== Aufgabe 1: Die Fibonacci-Folge ===== Die [[https://en.wikipedia.org/wiki/Fibonacci_sequence|Fibonacci-Folge]] ist wie folgt definiert: $$ f_0 = 1 $$ $$ f_1 = 1 $$ $$ f_n = f_{n-2} + f_{n-1}\ \ \mathrm{für}\ \ n > 1 $$ Jedes Folgenglied ist also die Summe der beiden vorhergehenden Folgenglieder. Hier die ersten Glieder: $$1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ \ldots$$ * Programmieren Sie eine Methode, die das n-te Glied der Fibonacci-Folge berechnet. Nutzen Sie dazu rekursive Methodenaufrufe und orientieren Sie sich am vorherigen Programm (Fakultätsberechnung). * Welchen wesentlichen Unterschied zum vorherigen Programm bemerken Sie? Wie wirkt er sich auf die obigen Diagramme zur Erklärung aus? [[.fibonacci:start|Musterlösung -> Bitte erst nach der Informatikstunde ansehen!]] ===== Aufgabe 2: größter gemeinsamer Teiler ===== Sind $a, b \in \mathbb{N}$, so lässt sich der größte gemeinsame Teiler von $a$ und $b$ ("ggT(a, b)") auf folgende Art rekursiv berechnen: \\ $ ggT(a, b) = $ * $a$, falls $a = b$, * $ggT(b, a-b)$, falls $ a > b$ und * $ggT(a, b - a)$, falls $a < b$. Schreiben Sie eine Klasse ''MyMathTools'' mit einer Methode ''ggT'', die den ggT zweier Zahlen auf die oben beschriebene Art berechnet! [[.ggtLoesung:start|Lösung]] ===== Aufgabe 3: Die Türme von Hanoi ===== Das Problem der Türme von Hanoi wird in diesem Video gut erklärt: {{ youtube>UMPneeBzQHk?large }} **Kurzgefasst:** \\ Vor Ihnen befinden sich drei Stäbe ("Türme"), wobei sich auf dem rechten der drei Stäbe ''n'' der Größe nach geordnete Scheiben befinden, die größte zuunterst. Die Aufgabe besteht darin, alle ''n'' Scheiben zum linken Stab zu bringen, wobei folgende Spielregeln gelten: * Bei jedem Schritt darf nur eine Scheibe bewegt werden. * Es darf **nie** zu einer Situation kommen, bei der auf einem der drei Stäbe eine größere Scheibe oberhalb einer kleinen zu liegen kommt. \\ \\ **Aufgabe 3: Die Türme von Hanoi** \\ Die drei Türme bekommen die Nummern 1, 2 und 3. \\ \\ Schreibe eine Klasse ''Hanoi'' mit einer Methode ''erkläreLösung(int startTurmNummer, int zielTurmNummer, int n)'', die in Textform erklärt, wie man ''n'' Scheiben unter Einhaltung der im Video erklärten Regeln vom Turm ''startTurmNummer'' zum Turm ''zielTurmNummer'' bringt. \\ \\ Die Ausgabe von ''erkläreLösung(1, 3, 4)'' soll beispielsweise so aussehen: Bewege eine Scheibe von Turm 1 zu Turm 2 Bewege eine Scheibe von Turm 1 zu Turm 3 Bewege eine Scheibe von Turm 2 zu Turm 3 Bewege eine Scheibe von Turm 1 zu Turm 2 Bewege eine Scheibe von Turm 3 zu Turm 1 Bewege eine Scheibe von Turm 3 zu Turm 2 Bewege eine Scheibe von Turm 1 zu Turm 2 Bewege eine Scheibe von Turm 1 zu Turm 3 Bewege eine Scheibe von Turm 2 zu Turm 3 Bewege eine Scheibe von Turm 2 zu Turm 1 Bewege eine Scheibe von Turm 3 zu Turm 1 Bewege eine Scheibe von Turm 2 zu Turm 3 Bewege eine Scheibe von Turm 1 zu Turm 2 Bewege eine Scheibe von Turm 1 zu Turm 3 Bewege eine Scheibe von Turm 2 zu Turm 3 **Lösungsidee/Tipps:** \\ * Bei gegebenen Turmnummern ''x'' und ''y'' (aus {1, 2, 3}) hat der übrige Turm dann immer die Nummer ''6 - x - y'' * Um ''n'' Scheiben von Turm ''x'' zu Turm ''y'' zu bewegen, bewege zuerst ''n - 1'' Scheiben von Turm ''x'' zu Turm ''6 - x - y'', dann eine (die größte!) Scheibe von Turm ''x'' zur Turm ''y'' und dann ''n - 1'' Scheiben von Turm ''6 - x - y'' zu Turm ''y''. Die Methode ''erkläreLösung'' muss sich also nur geeignet selbst aufrufen. [[.hanoi:loesung:start1832|Lösung]] \\ ===== Beispiel 2: Die Kochkurve ===== Die **Kochkurve** und die aus ihr gewonnene Kochsche Schneeflocke werden [[https://de.wikipedia.org/wiki/Koch-Kurve|in diesem Wikipedia-Artikel]] schön beschrieben. Die Kochkurve ergibt sich, indem man von einer waagrechten Strecke ausgeht und bei jedem Iterationsschritt jede Strecke folgendermaßen ersetzt: {{ :rekursion:pasted:20240908-142937.png?300 }} Die **Kochsche Schneeflocke** erhält man, wenn man von einem gleichseitigen Dreieck ausgehend dieselbe Iterationsvorschrift immer wieder anwendet.
===== Aufgabe 4: Fraktaler Baum ===== Erstelle mit Hilfe rekursiver Methodenaufrufe ein Programm, das einen fraktalen Baum zeichnet. Hier die Zeichnung nach der 12. Iteration: \\ {{ :rekursion:pasted:20240908-150155.png }} \\ Die Zeichnung beginnt mit einer vertikalen Linie und folgt folgender Iterationsvorschrift: \\ {{ :rekursion:fraktaler_baum.svg?600 |}} \\ **Tipps:** \\ * Es ist empfehlenswert, die rekursive Methode so zu programmieren, dass sie die Turtle vor ihrer Beendigung genau in den Zustand (d.h. Richtung, Position) bringt, in dem sie bei ihrem Aufruf war. * Mit der Methode ''penUp()'' können Sie den Stift der Turtle anheben, so dass sie nicht mehr zeichnet. Mit der Methode ''penDown()'' kannst Du ihn wieder herabsenken, so dass die Turtle wieder zeichnet. [[.fraktalerBaum:start6048|Lösung]] **Für Interessierte:** \\ \\ Neben der Kochkurve und fraktalen Bäumen gibt es viele weitere schöne [[https://de.wikipedia.org/wiki/Fraktal|fraktale]] Punktmengen, die mit wenig Aufwand durch einfach rekursive Methoden gezeichnet werden können: * [[https://de.wikipedia.org/wiki/Drachenkurve|Die Drachenkurve]] * [[https://de.wikipedia.org/wiki/Hilbert-Kurve|Die Hilbertkurve]] * usw. Lassen Sie sich herausfordern! ===== Weiteres Beispiel (für Interessierte): Quicksort ===== **Für Interessierte:** Quicksort \\ Stellen Sie sich ein Array mit ''n'' Elementen (z.B. Zahlen oder Zeichenketten) vor, das es zu (numerisch bzw. alphabetisch) zu sortieren gilt. Bei zufälliger Verteilung ist [[https://de.wikipedia.org/wiki/Quicksort|Quicksort]] im Mittel der schnellste Algorithmus für diesen Zweck. [[.quicksort:start|Hier ist der Algorithmus erklärt und implementiert.]] ===== Aufgabe 5: Floodfill ===== Gegeben ist eine Pixelgrafik mit einem beliebig geformten, zusammenhängenden Gebiet von Pixeln einer Farbe. Gesucht ist ein Algorithmus, der - ausgehend von einem Pixel dieses Gebietes - alle damit verbundenen Pixel gleicher Farbe rot färbt. \\ \\ Ein Algorithmus, der dieses Problem löst, ist **Floodfill**. Er existiert in einer rekursiven Variante, die [[https://de.wikipedia.org/wiki/Floodfill|hier sehr anschaulich erklärt ist.]] \\ \\ Gegeben ist das Programmgerüst unten, bei dem bereits dafür gesorgt ist, dass bei Mausklick auf den Punkt (x, y) die Methode ''fill(x, y, newColor)'' aufgerufen wird. Ergänzen Sie die Methode ''fillIntntern'' so, dass ausgehend vom Punkt (x, y) alle gleichfarbigen, damit verbundenen Punkte in der neuen Farbe eingefärbt werden.
[[.floodfillloesung:start1285|Lösung]] {{ .:pasted:20251006-100314.png}} ===== Aufgabe 6: Berechnung von Binomialkoeffizienten ===== Im Bild rechts sehen Sie das Pascalsche Dreieck. Die Einträge lassen sich durch folgende Regeln ganz einfach ermitteln: * (i) Der erste und letzte Eintrag jeder Reihe hat den Wert 1. * (ii) Den Wert der Einträge dazwischen erhält man, indem man die Werte der Einträge links und rechts darüber addiert (dargestellt durch die grauen Pfeile). Ihre Aufgabe ist es, eine rekursive Methode ''int pascal(int zeile, int spalte)'' zu erstellen, die einen beliebigen Eintrag der Pyramide berechnen kann. \\ Wie die Parameter Zeile und Spalte definiert sind, ersehen Sie aus folgender tabellenartiger Struktur: {{ .:pasted:20251006-100535.png }} Beispielsweise ergibt pascal(4, 2) den Wert 6. Erstellen Sie die Methode pascal! [[.pascal:start|Lösung]]