If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

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 Sierpinksi 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:
Sierpinski Dreieck 2 x 2
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:
Sierpinski Dreieck 4 x 4
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.
Sierpinski Dreieck 8 x 8
Sierpinski Dreieck 16 x 16
Sierpinski Dreieck 32 x 32
Sierpinski Dreieck 64 x 64
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:
Das Sierpinksi Dreieck
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:
    1. Zeichne ein Sierpinski-Dreieck, im oberen linken Quadrat.
    2. Zeichne ein Sierpinski-Dreieck, im Quadrat oben rechts.
    3. 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.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.