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:

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.