Rekursion: (Weihnachts-)Bäume und Schneeflocken
Einführung am Beispiel
Gemeinsames angeleitetes Programmieren: Baumwachstum simulieren, von Jahr zu Jahr.
Programm-Gerüst:
- baum.py
from turtle import * STAMMLAENGE = 380 speed(0) # hideturtle() penup() left(90) backward(STAMMLAENGE) pendown() exitonclick() # Um die Zeichung schneller erscheinen zu lassen, # gibt es den folgenden Trick: # Ersetze die Zeile ''speed(0)'' durch ''tracer(0)'' # und ergänze in der Zeile vor ''exitonclick()'', # also nach allen Zeichenbefehlen, die Zeile ''update()''.
Experimentiere:
- Für welche Verzweigungswinkel kommt eine besonders schöne Figur heraus? (Es gibt zwei “besonders schöne Winkel”.)
- Nimm statt 3 Verzweigungen eine andere Zahl von Verzweigungen.
- Zeichne jede der Verzweigungen unterschiedlich lang.
- Variiere die Winkel bei den rekursiven Aufrufen; nett ist es beispielsweise, den Winkel bei jedem rekursiven Aufruf zu verdoppeln (und die Längen wie üblich zu halbieren).
- Eventuell kann man auch Verzweigungen in den Stamm einbauen.
- Wer will, kann auch bereits hier eine Schleife über gewisse Verzweigungswinkel laufen lassen (auch wenn das eigentlich erst unten in der Animationsaufgabe vorgeschlagen wird…)
- Sei kreativ!
Eine Funktion heisst rekursiv, wenn sie sich selbst aufruft.
Rekursion meint in der Informatik (und ähnlich in der Mathematik) den Einsatz rekursiver Funktionen.
Etymologie: lateinisch recurrere, zurücklaufen, auf etwas zurückkommen
Aufgabe zur Rekursion: Koch-Kurve und kochsche Schneeflocke
Schreibe eine rekursive Funktion kochkurve(level, a)
, die je nach “Level” die folgenden Bilder zeichnet (alle Winkel sind entweder $60^\circ$ oder $120^\circ$; die Turtle soll jeweils links starten und rechts ihren Weg beenden, jeweils mit Blickrichtung nach rechts (und nicht wie beim “Baum” zum Ausgangspunkt zurückkehren); ACHTUNG (machen erfahrungsgemäss viele sonst anders): Der Anfangspunkt der Turtle soll vom Endpunkt immer (unabhängig vom Level) dieselbe Distanz haben; wenn man diese Kurve “unendlich genau” zeichnet, bekommt man die sogenannte Koch-Kurve):
Programm-Gerüst:
- koch-kurve.py
from turtle import * LEVEL = 3 SEITENLAENGE = 400 def kochkurve(level, a): # "kochkurve(0, a)" soll eine Strecke der Länge a zeichnen, wobei # die Schildkröte NICHT zurück zum Ausgansgspunkt geht (wie beim Baum oben). # Bei allen "höheren Kochkurven" "kochkurve(>0, a)" soll der Abstand vom Startpunkt # der Turtle bis zu ihrem Endpunkt genau a Pixel betragen. print('Hier ist die rekursive Funktion "kochkurve" zu definieren!') def schneeflocke(level, a): # Verwende die Funktion "kochkurve" dreimal, um die Schneeflocke zu zeichnen. print('Hier ist die Funktion "schneeflocke" zu definieren!') speed(0) # hideturtle() penup() backward(SEITENLAENGE/2) pendown() linienzug(LEVEL, SEITENLAENGE) # left(60) # schneeflocke(LEVEL, SEITENLAENGE) exitonclick()
Mit dieser Vorarbeit ist es nun einfach, eine Funktion schneeflocke
zu definieren, die die sogenannte Kochsche Schneeflocke zeichnet (ersetze die drei Seiten eines gleichseitigen Dreiecks durch Koch-Kurven):
Aufgabe zur Rekursion: Pythagoras-Baum
Schreibe eine rekursive Funktion pythagoras_baum
, die je nach “Level” die folgenden Bilder zeichnet. Die Turtle startet jeweils links unten mit Blickrichtung nach rechts und endet rechts unten mit Blickrichtung nach rechts.
Hinweis: Die Bilder sind mit dem Winkel $\alpha = 35^\circ$ gemalt (übliche Bezeichnungen für rechtwinklige Dreiecke). Die Kathetenlängen $a$ und $b$ haben in Abhängigkeit von $c$ und $\alpha$ die folgenden Werte: $$b = \cos(\alpha) \cdot c$$ $$a = \sin(\alpha) \cdot c$$
Wenn du Pyhon diese Werte berechnen lassen willst, musst die die Bibliothem math
importieren und kannst dann folgendes schreiben:
from math import * alpha = 35 b = cos(radians(alpha)) * c a = sin(radians(alpha)) * c
Du kannst den Pythagoras-Baum auch variieren. Hier einige Ideen:
- Die Äste nicht quadratisch, sondern rechteckig zeichnen.
- Die inneren Linien weglassen.
- Statt eines rechtwinkligen Dreiecks ein beliebiges anderes Dreieck nehmen (mit $a<c$ und $b<c$, damit der Baum “kleiner” wird). Um die Seitenlängen $a$ und $b$ in Abhängigkeit von $c$, $\alpha$, $\beta$ und $\gamma =180^\circ - \alpha - \beta$ zu berechnen, empfehle ich den Sinussatz:
$$\frac a{\sin \alpha} = \frac b{\sin \beta} = \frac c{\sin \gamma}$$
Aufgabe: Animation der obigen Objekte - "Filmchen drehen"
Animiere die Objekte, die wir oben gezeichnet haben:
- Zeichne nacheinander den Baum für verschiedene Verzweigungswinkel, etwa bei 30 Grad startend bis 120 Grad in Schritten von 1 Grad.
- Lass die Kochsche Schneeflocke rotieren.
Verstehe dazu eines der unten angegebenen Animations-Beispielprogamme ein bisschen und verändere es, indem du an geeigneter Stelle die Funktion zum Baum-Zeichnen bzw. zum Schneeflocke-Zeichnen aufrufst.
Die wichtigen Befehle in diesen Programmen sind tracer(0)
und update()
. Sie sorgen dafür, dass alle Zeichnungen “im Hintergrund” entstehen und erst per Update sichtbar werden. So vermeidet man das Flackern des Bildschirms. Ausserdem wird deutlich schneller gezeichnet.
gif-Datei aus Animation erstellen (zumindest unter Linux geht es so...)
to be written down
Weitere Programmierideen
Vielleicht ganz nett, falls jemand Spass am Python-Programmieren bekommen hat: 190 Python projects
Baum-Programm aus Lektion
- baum.py
from turtle import * def baum0(a): forward(a) backward(a) def baum1(a): forward(a) left(winkel) baum0(a/2) right(winkel) baum0(a/2) right(winkel) baum0(a/2) left(winkel) backward(a) def baum2(a): forward(a) left(winkel) baum1(a/2) right(winkel) baum1(a/2) right(winkel) baum1(a/2) left(winkel) backward(a) def baum(level, a): if level == 0: forward(a) backward(a) else: forward(a) left(winkel) baum(level - 1, a/2) # Selbstaufruf der Funktion # rekursive Funktion # recurrere = zurücklaufen right(winkel) baum(level - 1, a/2) right(winkel) baum(level - 1, a/2) left(winkel) backward(a) stammlaenge = 250 winkel = 30 tracer(0) # hideturtle() left(90) backward(stammlaenge) # baum2(stammlaenge) baum(8, stammlaenge) update() exitonclick()