lehrkraefte:snr:informatik:glf23:python:rekursion [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
~~NOTOC~~

====== Rekursion: (Weihnachts-)Bäume und Schneeflocken ======

===== Einführung am Beispiel =====

<WRAP center round todo 100%>
Gemeinsames angeleitetes Programmieren: Baumwachstum simulieren, von Jahr zu Jahr.

<hidden Anweisung für Lehrer:>
Sukzessive die Funktionen ''baum0'', ''baum1'', ''baum2'', ''baum3'', ... schreiben und mit Skizzen erklären: Am Anfang Skizze eines "Baum3" und erklären, wie er sich aus drei "Baum2"en zusammensetzt etcetera (Selbstähnlichkeit erwähnen). 

Bei konzentrationsschwachen Klassen: Bevor die rekursive Funktion ''baum'' erklärt wird, die S in neuem Programm ''koch0'', ''koch1'', etcetera schreiben lassen. Dann ''baum'' erklären und die S ''koch'' schreiben lassen.

Idee, um das Schreiben "unendlich vieler" Funktionen zu vermeiden: Ersetze die Zahl im Funktionsnamen durch einen Parameter (etwa namens ''level'') in einer neuen Funktion ''baum''. Beim rekursiven Aufruf als Kommentar etwas dahinterschreiben wie ''# Selbstaufruf = rekursiver Aufruf der Funktion''.


Alle Funktionen haben die aktuelle Streckenlänge als Parameter ''a''. Eventuell zusätzlich den Winkel als Parameter übergeben (bei ''baum0'' wird er nicht verwendet). 

Beim Programmieren Hotkeys erläutern: Markieren per Shift+Pfeiltasten, Einrücken von markiertem Block per Tab oder "Ausrücken" per Shift+Tab.

Einige S schreiben schnell selbst ''baum3'', ''baum4'' etc. und fragen dann, wie man die Turtle schneller zeichnen lassen kann, so dass man ''tracer(0)'' und ''update()'' erklären kann (siehe Programm ganz unten auf dieser Seite; ''hideturtle()'' ist dann wohl unnötig). 
</hidden>

{{:lehrkraefte:snr:informatik:glf22:python:baum-0.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:baum-1.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:baum-2.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:baum-3.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:baum-4.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:baum-5.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:baum-6.png?200|}}

Programm-Gerüst:

<code python 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()''.
</code>

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!
</WRAP>

<WRAP center round info>
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
</WRAP>

===== Aufgabe zur Rekursion: Koch-Kurve und kochsche Schneeflocke =====


<WRAP center round todo>
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 [[https://de.wikipedia.org/wiki/Koch-Kurve|Koch-Kurve]]):

{{:lehrkraefte:snr:informatik:glf22:python:kochlinie-0.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:kochlinie-1.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:kochlinie-2.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:kochlinie-3.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:kochlinie-4.png?200|}}
{{:lehrkraefte:snr:informatik:glf22:python:kochlinie-5.png?200|}}

Programm-Gerüst:
<code python 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()
</code>

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):

{{:lehrkraefte:snr:informatik:glf22:python:kochflocke-5.png?400|}}
</WRAP>

===== Aufgabe zur Rekursion: Pythagoras-Baum =====


<WRAP center round todo>
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.

{{:lehrkraefte:snr:informatik:glf23:python:pythagoras-innere_striche_true-tiefe_0.png?300|}}
{{:lehrkraefte:snr:informatik:glf23:python:pythagoras-innere_striche_true-tiefe_1.png?300|}}
{{:lehrkraefte:snr:informatik:glf23:python:pythagoras-innere_striche_true-tiefe_2.png?300|}}
{{:lehrkraefte:snr:informatik:glf23:python:pythagoras-innere_striche_true-tiefe_3.png?300|}}
{{:lehrkraefte:snr:informatik:glf23:python:pythagoras-innere_striche_true-tiefe_4.png?300|}}
{{:lehrkraefte:snr:informatik:glf23:python:pythagoras-innere_striche_true-tiefe_5.png?300|}}
{{:lehrkraefte:snr:informatik:glf23:python:pythagoras-innere_striche_true-tiefe_14.png?300|}}

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:
<code python>
from math import *

alpha = 35

b = cos(radians(alpha)) * c
a = sin(radians(alpha)) * c
</code>

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 [[https://de.wikipedia.org/wiki/Sinussatz|Sinussatz]]: 

$$\frac a{\sin \alpha} = \frac b{\sin \beta} = \frac c{\sin \gamma}$$

{{:lehrkraefte:snr:informatik:glf23:python:pseudopythagoras.png?400|}}

</WRAP>

===== Aufgabe: Animation der obigen Objekte - "Filmchen drehen" =====

<WRAP center round todo>
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.

<hidden Animations-Beispielprogramm (einfache Variante)>
<code python animierter-kreis.py>
from turtle import *
from time import *

tracer(n=0)
hideturtle()

for radius in range(-200, 201):
    clear()
    circle(radius)
    update()
    sleep(0.01)
</code>
</hidden>

<hidden Animations-Beispielprogramm (kompliziertere Variante, Animation läuft bis zum Abbruch per Mausklick oder Tastendruck)>
<code python animierter-kreis-abbruch-per-click-oder-tastendruck.py>
from turtle import *
from time import *

def abbruch(x=0, y=0):
    global aktiv
    aktiv = False

leinwand = Screen()
tracer(n=0)
hideturtle()
leinwand.onkeypress(abbruch)
leinwand.onclick(abbruch)
listen()

aktiv = True
radius = 20
veraenderung = 1
while aktiv:
    clear()
    circle(radius)
    update()
    if radius < -200 or radius > 200:
        veraenderung = -veraenderung
    radius = radius + veraenderung
    sleep(0.01)
</code>
</hidden>

{{:lehrkraefte:snr:informatik:glf22:python:baum.gif?400|}}
{{:lehrkraefte:snr:informatik:glf22:python:flocke.gif?400|}}

</WRAP>

===== 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: [[https://amankharwal.medium.com/130-python-projects-with-source-code-61f498591bb|190 Python projects]]
====== Baum-Programm aus Lektion ======

<code python 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()
</code>

<!--
<code python baum.py>
from turtle import *

STAMMLAENGE = 380

def baum0(a):
    forward(a)
    backward(a)

def baum1(a, winkel):
    forward(a)

    left(winkel)
    baum0(a/2)
    right(winkel)
    baum0(a/2)
    right(winkel)
    baum0(a/2)
    left(winkel)

    backward(a)

def baum2(a, winkel):
    forward(a)

    left(winkel)
    baum1(a/2, winkel)
    right(winkel)
    baum1(a/2, winkel)
    right(winkel)
    baum1(a/2, winkel)
    left(winkel)

    backward(a)

def baum(level, a, winkel):
    if level == 0:
        forward(a)      # alte Funktion baum0
        backward(a)
    else:
        forward(a)

        left(winkel)
        baum(level - 1, a/2, winkel)
        right(winkel)
        baum(level - 1, a/2, winkel)
        right(winkel)
        baum(level - 1, a/2, winkel)
        left(winkel)

        backward(a)

speed(0)
# hideturtle()
penup()
left(90)
backward(STAMMLAENGE)
pendown()
baum(6, STAMMLAENGE, 30)

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()''.
</code>
-->

===== Link zur Kursseite =====

[[lehrkraefte:snr:informatik:glf23|Zur Kursseite]]