Hauptinhalt
Informationstechnik
Kurs: Informationstechnik > Lerneinheit 1
Lektion 6: Rekursive Algorithmen- Rekursion
- Die Fakultät
- Challenge: Iterative Fakultät
- Rekursive Fakultät
- Challenge: Rekursive Fakultät
- Eigenschaften von rekursiven Algorithmen
- Verwende Rekursion zum bestimmen ob ein Wort ein Palindrom ist
- Challenge: Ist ein String ein Palindrome?
- Die Potenzen einer Zahl berechnen
- Challenge: Rekursive Potenzen
- Mehrere Rekursionen mit dem Sierpinski-Dreieck
- Die Effizienz von rekursiven Funktionen verbessern
- Projekt: Rekursive Kunst
© 2023 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung
Mehrere Rekursionen mit dem Sierpinski-Dreieck
Bisher haben wir Rekursionsbeispiele betrachtet, die auf jeder Ebene nur einen rekursiven Anruf verlangt haben. Aber manchmal werden mehrere rekursive Anrufe gebraucht. Hier ist ein gutes Beispiel, ein mathematisches Konstrukt, das ein Fraktal ist, bekannt als Sierpinski-Dreieck :
Das Sierpinski Dreieck ist eine Anzahl von kleinen Quadraten, die in einem bestimmten Muster in einer quadratischen Region gezeichnet werden. Es wird folgendermaßen konstruiert: Beginne mit der gesamten Quadrat und teilen Sie sie in vier Abschnitte wie folgt auf:
Nimm' nun drei Quadrate (die mit einem Kreuz gekennzeichnet sind) - das oben links, oben rechts und unten rechts - und teile sie jeweils in vier Abschnitte in der gleichen Weise wie folgt:
Fahre in dieser Weise fort: Teile jedes markierte Quadrat in vier Abschnitte, und markiere die entstandenen Quadrate oberen links, oben rechts und unten rechts mit einem Kreuz, aber nie die das Quadrat unten links.
Sobald die Quadrate klein genug sind, höre auf zu teilen. Wenn du jedes Quadrat mit einem X ausfüllst und alle anderen Quadrate vergissst, erhältst du ein Sierpinski Dreieck. Hier ist es noch einmal:
Wir fassen zusammen, wie man ein Sierpinski Dreieck in ein Quadrat zeichnet:
- Bestimme die Größe des Quadrats. Wenn es klein genug ist, um ein Basisfall zu sein, dann füllen das Quadrat einfach aus. Du kannst im Vorfeld bestimmen, wie klein "klein genug" ist.
- Andernfalls teile das Quadrat in vier Teile: oben links, oben rechts, unten rechts und unten links. "Löse" rekursiv drei Unterprobleme:
- Zeichne ein Sierpinski-Dreieck, im oberen linken Quadrat.
- Zeichne ein Sierpinski-Dreieck, im Quadrat oben rechts.
- Zeichne ein Sierpinski-Dreieck, im unteren rechten Quadrat.
Dazu muß man nicht nur einen, sondern drei rekursive Anrufe machen. Deshalb betrachten wir ein Sierpinski-Dreieck, um Mehrfach-Rekursion zu erklären.
Du kannst drei der vier Quadrate beliebig wählen, in denen du rekursiv Sierpinski-Dreiecke zeichnen möchtest. Das Ergebnis wird ein Vielfaches einer Drehung von 90 Grad sein. (Wenn du rekursiv Sierpinski Dreiecke in irgendeine andere Anzahl von Quadraten zeichnest, erhältst du kein interessantes Ergebnis.)
Das Programm unten zeichnet ein Sierpinski-Dreieck. Versuche einige der rekursiven Aufrufe zu kommentieren und auskommentieren um rotierte Dreiecke zu erhalten:
Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.