Lijnenspel

Recursief lijnen trekken

Lijnen trekken

Etch-A-Sketch, misschien ken je het wel? Met twee draaiknoppen kan je op een scherm horizontale en verticale lijnen trekken en met wat oefeningen kan je ze ook laten buigen door beide knoppen tegelijkertijd te draaien.

“Etch-a-Sketch has a lot of unique limitations and one of the big ones is that everything is connected by a single line.”

Lijnen met Python

Kan het? Ja het kan!

Voorbeeld

from turtle import *

def poly(runs, TOTAL_SIDES):
    """Teken een polygoon met runs/TOTAL_SIDES
    """
    if runs == 0:
        return  # klaar
    else:
        forward(100)
        left(360 / TOTAL_SIDES)
        poly(runs - 1, TOTAL_SIDES)


poly(9, 9)
exitonclick()

Een recursief turtle voorbeeld! De functie poly accepteert twee parameters, de run parameter bepaalt hoe vaak de functie zichzelf moet aanroepen en TOTAL_SIDES is het aantal zijden van de polygoon. Kan je de base case en de recursieve case aanwijzen?

TOTAL_SIDES noemen we in dit geval een constante, een onveranderlijke waarde. Deze waarde moet natuurlijk onveranderlijk zijn omdat de functie deze waarde bij elke aanroep nodig heeft om de hoek van de draai te berekenen. Het is een conventie (een gewoonte, of stilzwijgende afspraak) om constante variabelen in hoofdletters te schrijven, niet alleen in Python maar ook in veel andere programmeertalen.

Random lijnen

from turtle import *
from random import choice

def rwalk(N):
    """Zet N keer 20 pixel stappen, naar NE of SE
    """
    if N == 0:
        return

    direction = choice(["left", "right"])

    if direction == "left":
        left(45)
        forward(20)
        rwalk(N - 1)
    else:
        right(45)
        forward(20)
        rwalk(N - 1)

Een random turtle walk! Maak (vanuit het perspectief van turtle) een draai naar noord-oost- (links) of zuid-oostelijke (rechts) richting, afhankelijk van een random keus.

De loop van een aangeschoten turtle…

Herhaling

Herhaling van handelingen maar herhaling in code?

if direction == "left":
    left(45)
    forward(20)
    rwalk(N - 1)
else:
    right(45)
    forward(20)
    rwalk(N - 1)

Het is geen probleem als je dit op deze manier schrijft (Python zal in ieder geval niet klagen!) maar je ziet dat we onszelf herhalen. Het enige dat de if en else van elkaar onderscheidt is de richting, de stap voorwaarts gevolgd door de recursieve aanroep is wat ze met elkaar gemeen hebben. Zou dit ook anders kunnen worden geschreven?

if direction == "left":
    left(45)
else:
    right(45)

forward(20)
rwalk(N - 1)

Dit is een herschreven versie. Het if / else blok is in nu alleen maar “verantwoordelijk” voor de richting en als dit blok is afgehandeld wordt vervolgens een stap voorwaarts gezet en wordt de volgende recursieve aanroep gedaan.

Nogmaals, is een herhaling zoals je in het eerste geval hebt gezien een probleem? Nee, maar misschien is de tweede variant beter leesbaar of maakt het in ieder geval duidelijker wat een keus voor links of rechts betekent (en maken we daarmee de bedoeling voor onszelf en wellicht ook andere lezers van onze oplossing expliciet).

Quiz

def chai(dist):
    """fn mysterie!
    """
    if dist < 5:
        return

    forward(dist)
    left(90)
    forward(dist / 2)
    right(90)

    right(90)
    forward(dist)
    left(90)

    left(90)
    forward(dist / 2.0)
    right(90)
    backward(dist)

Wat is het resultaat van chai(100)?

Pak een stuk papier en probeer de lijn te trekken en het resultaat uit te tekenen! 100 is in dit geval natuurlijk het aantal pixels op scherm, kies op papier bijvoorbeeld voor ~10cm.

Oplossing

Vervolg

def chai(dist):
    """fn mysterie onthuld!
    """
    if dist < 5:
        return

    forward(dist)
    left(90)
    forward(dist / 2)
    right(90)
    
    chai(dist / 2)  # <== !!!
    
    right(90)
    forward(dist)
    left(90)

    left(90)
    forward(dist / 2.0)
    right(90)
    backward(dist)

In het eerste voorbeeld (de quiz) zag je twee witregels. Wat gebeurt er als we een eerste recursieve aanroep doen? Je zal zien dat het patroon dat je net hebt uitgetekend zich gaat herhalen!

Laten we zien wat er gebeurt als we de recursieve aanroep alleen op de tweede witregel plaatsen.

def chai(dist):
    """fn mysterie onthuld!
    """
    if dist < 5:
        return

    forward(dist)
    left(90)
    forward(dist / 2)
    right(90)
        
    right(90)
    forward(dist)
    left(90)

    chai(dist / 2)  # <== !!!
    
    left(90)
    forward(dist / 2.0)
    right(90)
    backward(dist)

Je ziet precies hetzelfde gebeuren (maar gespiegeld). Laten we ze nu combineren!

def chai(dist):
    """fn mysterie onthuld!
    """
    if dist < 5:
        return

    forward(dist)
    left(90)
    forward(dist / 2)
    right(90)
        
    chai(dist / 2)  # <== !!!

    right(90)
    forward(dist)
    left(90)

    chai(dist / 2)  # <== !!!
    
    left(90)
    forward(dist / 2.0)
    right(90)
    backward(dist)

En daar zien je het volledig recursief patroon!