Rekursive Schildkröten in Python 

Ein Baum

Das folgenden Programm zeigt das Zeichnen eines Baumes, welches dadurch realisiert wird, daß die einzelnen Zweige rekursiv wieder als Baum gezeichnet werden. Dabei ist es wichtig, daß die Schildkröte am Ende des Zeichnens eines Baums wieder mit der gleichen Richtung wie am Anfang genau dort ist wie am Anfang.

Ein Baum wird zunächst wie ein „Y“ gezeichnet. Dann wird jeder der beiden Zweige rekursiv wieder wie ein Baum gezeichnet, und so weitere.

Programm

from turtle import *
def tree( length, depth ):
    if depth:
        forward( length )
        a = 25
        l = length/1.6
        left(  a ); tree( l, depth-1 ); right( a );
        right( a ); tree( l, depth-1 ); left(  a ); 
        backward( length )
    else:
        forward( length )
        backward( length )
    
tree( 100, 6 )

Das folgenden Programm zeigt eine etwas kompliziertere Variation des Baumes.

main.py

from turtle import *
from random import random
speed( False )
def tree( length, depth ):
    if depth:
        color(.7-depth/10,.7-depth/10,.7-depth/10)
        pensize( depth )
        forward( length*.5 )
        a = 25 + 15*( random()-0.5 )
        l = length/1.6 *( 1 + 0.3*( random()-0.5 ))
        left( a );  tree( l, depth-1 ); right( a );
        a = 25 + 15*( random()-0.5 )
        l = length/1.6 *( 1 + 0.3*( random()-0.5 ))
        right( a ); tree( l, depth-1 ); left( a ); 
        backward( length*.5 )
        depth += 1
        pensize( depth )
        color(.7-depth/12,.7-depth/12,.7-depth/12)
    else:
        forward( length*.5 )
        backward( length*.5 )
    
left( 90 )
penup(); backward( 200 ); pendown()
tree( 300, 7 )
hideturtle()

lambda-Inkarnationen

Die folgende Definition von »triangle_line« mit einer lambda-Inkarnation ist etwas eleganter (da die vierfach wiederholte Anweisung einfacher ist), aber vielleicht weniger verständlich.

main.py

from turtle import *
def direct_line( length ):
    forward( length )
def triangle_line( length, depth ):
    if depth < 1:
        direct_line( length )
    else:
        recurse = lambda: triangle_line( length/3, depth-1 )
        recurse(); left( 60 )
        recurse(); right( 60 + 60 )
        recurse(); left( 60 )
        recurse()
triangle_line( 200, 1 )

Übungsaufgaben

/   Übungsaufgabe

Schreiben Sie eine Definition einer Funktion, die mit »Beep« aus dem Modul »winsound« eine Melodie – ausgehend von einem als Argument übergebenen Grundton ausgibt: Zuerst soll der Grundton erklingen, dann die Quinte über dem Grundton, dann die kleine Terz über dem Grundton und schließlich wieder die Quinte. Benutzen Sie zur Ausgabe eines bestimmten Tons dann aber wieder (bis zu einer gewissen Tiefe von etwa 4) rekursiv dieselbe Funktion, so daß sich eine „rekursive Melodie“ ergibt.

/   Übungsaufgabe

Schreiben Sie eine Funktion die eine Note zeichnet. Die Höhe und Dauer der Note soll beim Aufruf als Parameter übergeben werden. Zunächst sollen nur die Noten C, D, E, F, G, A und H als Ganztöne (Töne mit der Dauer eines ganzen Zeitwertes) gezeichnet werden. Bei jedem Aufruf der Funktion (außer beim ersten), soll die Note etwas weiter rechts gezeichnet werden. Schreiben Sie dann noch eine Funktion, welche die Notenlinien zeichnet. Erweitern Sie die Funktion dann, so daß auch halbe Töne (Töne mit der Dauer eines halben Zeitwertes) gezeichnet werden können. Sie könne Ihre Bibliothek im Laufe der Zeit erweitern, um immer mehr Arten verschiedener Tönnen zeichnen zu können.

Die Koch -Kurve

Als IDLE -Datei ausführen:

main.py

from turtle import *
def direct_line( length ):
    forward( length )
def triangle_line( length ):
    direct_line( length/3 )
    left( 60 )
    direct_line( length/3 )
    right( 60 + 60 )
    direct_line( length/3 )
    left( 60 )
    direct_line( length/3 )
direct_line( 200 )
backward( 200 )
triangle_line( 200 )

In dem folgende Programm wird zum Zeichen von Linien, die nicht zu kurz sind, immer wieder »triangle_line« verwendet, wodurch eine Kurve mit einer interessanten Struktur entsteht. (Man ersetze die Zahl »1« in »triangle_line( 200, 1 )« unten durch »2«, »3« oder »4«.)

main.py

from turtle import *
def direct_line( length ):
    forward( length )
def triangle_line( length, depth ):
    if depth < 1:
        direct_line( length )
    else:
        triangle_line( length/3, depth-1 ); left( 60 )
        triangle_line( length/3, depth-1 ); right( 60 + 60 )
        triangle_line( length/3, depth-1 ); left( 60 )
        triangle_line( length/3, depth-1 )
triangle_line( 200, 1 )

Eine Funktion, die sich unter Umständen selber aufruft, wird rekursiv genannt. Unsere rekursive Funktion zeichnet eine Kurve, die sich (nährungsweise) (verkleinert) selber enthält. Die hier gezeichnete Kurve ist eine Annäherung an die Koch -Kurve.

Die Grammatik von Python  ist rekursiv, da eine if-Anweisung beispielsweise selber wieder eine if-Anweisung enthalten kann. Entsprechend enthält eine Python -Implementation rekursive Funktionen zur Analyse von Python -Programmen. Rekursive Funktionen spielen also eine wichtige Rolle in der Informatik.

Beschleunigung

Das Zeichnen kann durch Auswertung von »speed( False )« vor »showturtle()« noch etwas beschleunigt werden.

Eine weitere starke Beschleunigung ist möglich, wenn direkt vor dem Zeichnen die Anzeige mit »tracer( 0 )« ausgeschaltet wird. Direkt nach dem Zeichnen kann die Anzeige dann mit »update()« einmal aktualisiert werden.

Wenn statt »tracer( 0 )« »tracer( 100 )« verwendet wird, so wird die Anzeige nur nach jeder hundertsten Zeichenaktion aktualisiert, was oft eine ausreichende Beschleunigung ergibt, aber es erlaubt, den Ablauf doch noch verfolgen zu können.

Die Koch -Schneeflocke

Wenn die vorletzte Zeile des obigen Programms durch die folgenden vier Zeilen ersetzt wird, erhält man eine Annäherung an eine Koch -Schneeflocke.

Quelltext

triangle_line( 200, 4 ); right( 360/3 )
triangle_line( 200, 4 ); right( 360/3 )
triangle_line( 200, 4 ); right( 360/3 )
hideturtle()