Rekursionen


Rekursion ist ein Lösungsverfahren, bei dem ein Problem auf das gleichartige, aber etwas vereinfachte Problem zurückgeführt wird. Eine Funktion ist dann rekursiv, wenn sie sich selbst aufruft. Damit sich eine rekursive Funktion nicht endlos aufruft, braucht sie eine Abbruchbedingung ("Verankerung"). Die Turtlegrafik eignet sich hervorragend für die Programmierung von Rekursionen. Es entstehen dabei sehr schöne Bilder.

Beispiel 1: Das Prinzip einer Rekursion kann anschaulich am Beispiel Zeichnen einer Treppe erklärt werden: Bei der rekursiven Lösung wird eine Treppe mit 6 Stufen aus einer Stufe und einer Treppe mit 5 Stufen zusammengesetzt, ein Treppe mit 5 Stufen kann auf eine Stufe und einer Treppe mit 4 Stufen zurückgeführt werden (usw). In der Funktion staircase(n) wird jeweils dieselbe Funktion staircase(n - 1) aufgerufen, wobei der Parameter bei jedem neuen Aufruf um 1 kleiner wird. Wenn die Abbruchbedingung n = 0 erfüllt ist, bricht das Programm ab.

 

 

 # Tu10.py

from gturtle import *

def step():
    forward(20)
    right(90)
    forward(20)
    left(90)

def staircase(n):
    if n == 0:
        return
    step()
    staircase(n-1)  

makeTurtle() 
staircase(6)  
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

Beispiel 2: Der binäre Baum


 
Das Zeichnen eines binären Baums lässt sich auf eine einfache Grundfigur zurückführen. Die Funktion tree() wird jeweils im linken und rechten Ast mit der halben Streckenänge s aufgerufen. Für s < 8 bricht die Rekursion ab.

# Tree.py

from gturtle import *

def tree(s):
    if s < 8:
        return
    forward(s)
    left(45)
    tree(s/2)
    right(90)
    tree(s/2)
    left(45)
    back(s)

makeTurtle()
setY(-100)
tree(128)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 

Es ist wichtig, dass die Turtle nach dem Zeichnen des Baums an ihren Ursprünglich Position und Blickrichtung zurückkehrt.

 

Beispiel 3: Wabenmuster
Wenn man die Länge der gezeichneten Linien immer gleich behält und den Drehwinkel 60° wählt erhält man einen schönen Wabenmuster.

# Wabenmuster.py

from gturtle import *

def wabe(s):
    if s == 0:
        return
    forward(a)
    left(60)
    wabe(s - 1)
    right(120)
    wabe(s - 1)
    left(60)
    back(a)

makeTurtle()
hideTurtle()
a = 20
s = 12
wabe(s)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 

 

Beispiel 4: Quadratmuster
Das erste Quadrat hat die Seitenlänge 64. Bei jedem weiteren Aufruf der Funktion figure() wird die Seitenlänge halbiert. Die Rekursion bricht ab, wenn s < 1 ist. Ergänzt man die Funktion figure() mit folgenden zwei Zeilen
figure(x - s, y - s, s/2)
figure(x + s, y - s, s/2)

so werden Quadrate auch im unteren Bereich gezeichnet. Mit gefüllten Quadraten entsteht ein schönes Teppichmuster.

 # SquarePattern.py

from gturtle import *

def square(s):
    for i in range(4):
        forward(s)
        right(90)

def figure(x, y, s):
    if s < 2:
        return
    setPos(x - s/2, y - s/2)
    square(s)
    figure(x + s, y + s, s/2)
    figure(x - s, y + s, s/2) 

makeTurtle()
speed(-1)
figure(0, 0, 64)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 

 

Beispiel 5: Koch-Kurve
Zum besseren Verständnis kann man die Anzahl Generationen auf 1, 2, oder 3 reduzieren:
1 Generation 2 Generationen 3 Generationen

# Koch.py

from gturtle import *

def koch(s, n):
    if n == 0:
        forward(s)
        return
    koch(s / 3, n - 1)
    left(45)
    koch(s / 3, n - 1)
    right(90)
    koch(s / 3, n - 1)
    left(45)
    koch(s / 3, n - 1)

makeTurtle()
hideTurtle()
setPos( -180, 0)
right(90)
koch(200, 4)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

Beispiel 6: Peano

  Peano ist eine der bekanntesten Rekursion. Das Problem lässt sich auf eine einfache Figur zurückführen.

 

 # Peano.py

from gturtle import *

def peano(n, s, w):
    if n == 0:   
        return
    lt(w)
    peano(n - 1, s, -w)
    fd(s)
    rt(w)
    peano(n - 1, s, w)
    fd(s)
    peano(n - 1, s, w)
    rt(w)
    fd(s)
    peano(n - 1, s, -w)
    lt(w)
    
makeTurtle()
setPos(185, -185)
speed(-1)
peano(6, 6, 90)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 

 

Beispiel 7: TreeFractal

Weniger bekannt ist das schöne Treefractal.

# TreeFractal.py

from gturtle import *

def tree(size):
    if size < 5:
        fd(size)
        bk(size)
        return
      
    fd(size / 3)
    lt(30)
    tree(size * 2 / 3)
    rt(30)
    fd(size / 6)
    rt(25)
    tree(size / 2)
    lt(25)
    fd(size / 3)
    rt(25)
    tree(size / 2)
    lt(25)
    fd(size / 6)
    bk(size)

makeTurtle()
ht()
setPos(20, -195)
tree(250)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 

 

 

Beispiel 8: FlowerFractal

FlowerFractal entsteht unter Einbezug des Befehls dot(). Ersetzt man in der letzen Zeile

figur(64, 60, 0)

den Winkel 60 durch 90 oder 120 entstehen weitere interessante Figuren.


# Tu10a.py

from gturtle import *

def figur(size, angle, turn):
    if size < 10:
        return
    while True:  
        flower(size, angle)
        turn = turn + angle
        if turn % 360 == 0:
            break       
def flower(size, angle):
    forward(size)
    dot(15)
    figur(size/2, -angle, 0)
    right(angle)    

makeTurtle()
setPos(-80, -80)
figur(64, 60, 0)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 

 

Beispiel 9: Sierpinsi Fraktal

Das schöne Dreick-Fraktal trägt den Namen nach dem polnischen Mathematiker Sirpinsky (1882-1969). Häufig wird es auch mit gefüllten Dreiecken gezeichnet. Dazu muss man in der Funktion Triagle ein gefülltes Dreieck zeichnen und n etwas kleiner wählen.


# Sierpi.py

from gturtle import *

def triangle(s):
   repeat 3:
      forward(s)
      left(120)   

def sierpi(n, s):
   if n == 0: 
      triangle(s)  
      return
   sierpi(n - 1, s / 2)
   forward(s / 2)
   sierpi(n - 1, s / 2)
   left(120)
   forward(s / 2)
   right(120)
   sierpi(n - 1, s / 2)
   left(60)
   back(s / 2)
   right(60)
    
makeTurtle()
n = 7
s = 400
hideTurtle()
setPos( -200, -190)
right(90)
sierpi(n, s)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 

 


Aufgaben Serie 10

 

1)
Erstelle die folgende Zeichnung mit Hilfe einer Rekursion.

 

 

 


2)
Erstelle die folgende Zeichnung mit Hilfe einer Rekursion.

 

 

 

 


3)

Ergänze den Programmcode so, dass eine Flocke gezeichnet wird.

def figure(s):
for i in range(6):
forward(s)
figure(s/3)
back(s)
right(60)

 

 


4)

Ergänze die Kochkurve so, dass eine ganze Schneeflocke entsteht.

 

Anleitung: Betrachte folgende Generationen::
 
 

5)

Die interessante Klothoide kann mit folgender rekursiven Funktion erstellt werden:

def clothoid(s):     
    if s > 1500:
return
forward(20)
left(0.025 * s)
clothoid(s + 10)

Ergänze den Programmcode und teste die Rekursion für verschiedene Parameter s.