rekursionen

17. REKURSIONEN

 

 

DU LERNST HIER...

 

dass Rekursion ein Lösungsverfahren ist, 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. Betrachte dieses Kapitel als Zusatzstoff und freue dich an schönen Bildern, die mit Rekursionen entstehen.

 

 

MUSTERBEISPIELE

 

Das Prinzip einer Rekursion kann anschaulich am Beispiel des Zeichnens einer Treppe erklärt werden: Eine Treppe mit 6 Stufen wird aus einer Stufe und einer Treppe mit 5 Stufen zusammengesetzt, ein Treppe mit 5 Stufen wird auf eine Stufe und einer Treppe mit 4 Stufen zurückgeführt (usw.). In der Funktion staircase(n) wird also jeweils dieselbe Funktion staircase(n - 1) aufgerufen. Wenn die Abbruchbedingung n = 0 erfüllt ist, bricht das Programm mit return ab.

  

► In Zwischenablage kopieren


 
Das Zeichnen eines binären Baums lässt sich auf eine einfache Grundfigur zurückführen.

Anschaulich gesagt ist ein binärer Baum mit der Stammlänge s ein Stamm und ein Links- sowie ein Rechtsbaum mit der Stammlänge s /2. Für die Stammlänge < 8 bricht die Rekursion ab.

  

► In Zwischenablage kopieren

Bemerkung: das back(s) ist wichtig, da nach dem Zeichnen des (Teil-)Baums die Turtle wieder im Anfangszustand sein muss.

 

 

MERKE DIR...
 

Die Rekursion ist ein wichtiges Lösungsverfahren, bei dem man ein Problem auf dasselbe, etwas vereinfachte Problem zurückführt und dieses in einem besonders einfachen Fall löst (bei Rekursionsabbruch). Rekursive Lösungsverfahren sind elegant, aber meist schwierig zu durchblicken.

 

 

ZUM SELBST LÖSEN


  1.

Überlege, wie du das Programm, das den binären Baum zeichnet (Beispiel 2) ändern musst, damit der nebenstehende Baum entsteht.

  

  2.

Ergänze den Programmcode so, dass eine Flocke gezeichnet wird. Gehe von folgendem Gerüst aus.

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

   


 

WEITERE BEKANNTE REKURSIONEN

 

Sirpinsky Fractal:

► In Zwischenablage kopieren

Flower Fractal:

► In Zwischenablage kopieren

Peano Fractal:

► In Zwischenablage kopieren