lehrkraefte:snr:informatik:glf23:python:rekursion

This is an old revision of the document!

Rekursion: (Weihnachts-)Bäume und Schneeflocken

Einführung am Beispiel

Gemeinsames angeleitetes Programmieren: Baumwachstum simulieren, von Jahr zu Jahr.

Anweisung für Lehrer:

Anweisung für Lehrer:

Sukzessive die Funktionen baum0, baum1, baum2, baum3, … schreiben und mit Skizzen erklären (wie setzt sich die Zeichnung von baum3 aus den anderen “Bäumen” zusammen?). Idee, um das Schreiben “unendlich vieler” Funktionen zu vermeiden: Ersetze die Zahl im Funktionsnamen durch einen Parameter (etwa namens level oder jahr) in einer neuen Funktion baum. Alle Funktionen haben die aktuelle Streckenlänge als Parameter a. Eventuell zusätzlich den Winkel als Parameter übergeben (bei baum0 wird er nicht verwendet).

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

Aufgabe zur Rekursion: Pythagoras-Baum

Schreibe eine rekursive Funktion pythagoras_baum, die je nach “Level” die folgenden Bilder zeichnet:

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:

Baum-Programm aus Lektion

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

Link zur Kursseite

Zur Kursseite

  • lehrkraefte/snr/informatik/glf23/python/rekursion.1701779934.txt.gz
  • Last modified: 2023/12/05 13:38
  • by Olaf Schnürer