Contents

TOPIC 7: Recursieve Structuren

Nadat we in een eerder topic uitgebreid bestudeerd hebben dat Python functies recursief kunnen zijn, verleggen we onze aandacht naar recursieve gegevens (ook wel recursieve structuren genoemd) in Python.

Inleiding

In algemeen taalgebruik is een recursieve structuur een structuur die elementen bevat die van precies dezelfde soort (lees: type) n als de structuur zelf. We kennen beslist volgende voorbeelden:

Verzamelingenleer:

In de wiskunde kunnen verzamelingen als elementen verzamelingen bevatten. Zo is bijvoorbeeld \(\{ \{1,2\}, \{3,4 \}\}\) een verzameling van 2 verzamelingen. Een verzameling kan dus een recursieve structuur zijn. In principe kan men deze redenering willekeurig diep doorzetten: \(\{ \{ \{ 1\}, \{2, 3\} \}, \{ 4 \} \}\) is een verzameling van verzamelingen waarbij de eerste verzameling opnieuw een verzameling van verzamelingen is. Enzovoort.

Famillierecht:

In het familierecht kan een persoon verschillende erfgenamen hebben die elk op hun beurt weer erfgenamen kunnen hebben. Ook hier staat er op het principe geen beperking en kan men in theorie bomen van erfgenamen tegenkomen van willekeurige diepte.

Rekenkunde:

Een binaire rekenkundige uitdrukking is een uitdrukking van de vorm \(operand_1~\Box~operand_2\) waarbij \(\Box\) een bewerking (ook wel operator genoemd) is die gebruik maakt van linker en een rechter operanden. Voorbeelden van \(\Box\) zijn \(+\), \(-\), \(*\), enzovoort. Elk van de operanden kunnen op hun beurt rekenkundige uitdrukkingen zijn. Zo kunnen we ingewikkelde rekenkundige uitdrukkingen bouwen waarvan de diepte niet a priori begrensd is. Bijvoorbeeld \(1 \Box 4\) maar ook \(((1 \Box 2) \Box (3 \Box 4))\) en \((((1 \Box 2) \Box (3 \Box 4)) \Box 5)\) zijn correcte rekenkundige uitdrukkingen.

Kenmerkend aan recursieve structuren is dat er in principe geen beperking staat op de diepte waarmee de structuur kan worden opgebouwd. Natuurlijk heeft ieder concreet voorbeeld wel een eindige diepte maar in de algemene beschrijving van de structuren kan men geen op voorhand vastgelegde diepte vooropstellen.

Wat ook belangrijk is, is dat de recursie in de structuur eindigt bij atomaire gegevens. Als alle elementen van een verzameling geen verzamelingen meer zijn maar gewoon atomaire “dingen” houdt de nesting op. Iedere concrete familieboom eindigt bij erfgenamen die geen zelf geen erfgenamen meer hebben. En een ingewikkelde binaire rekenkundige uitdrukking eindigt ooit bij operanden die niet opnieuw uit uitdrukkingen bestaan maar wel uit gewone getallen.

We besluiten dus dat een recursieve structuur een structuur is waarvan de elementen op hun beurt weer recursieve structuren kunnen zijn. Voor ieder concreet voorbeeld stopt de recursie wanneer de onderdelen atomaire gegevens zijn. In de algemene beschrijving van recursieve structuren kan er echter geen op voorhand vastgelegde grens zijn w.b. de diepte van de structuur.

Er zijn drie aspecten omtrent recursieve structuren die het bestuderen waard zijn:

Voorstelling

Ten eerste dienen we te bestuderen hoe we recursieve structuren kunnen voorstellen in Python. De basistruuk voor het bouwen van recursieve structuren bestaat uit het maken van tupels of lijsten waarvan de componenten zélf ook weer tupels of lijsten zijn. Dit wordt nesting genoemd.

Verwerking

Het is natuurlijk de bedoeling dat we iets nuttigs kunnen doen met een recursieve structuur. Dat zullen we uiteraard doen door Python functies te schrijven die een recursieve structuur als invoer nemen of die een recursieve structuur als resultaat opleveren (of beide). Zoals we zullen zien zijn zulke functies vaak op een natuurlijke manier recursief.

Beschrijving

Ieder genest tupel en/of lijst is maar een concreet voorbeeld van een recursieve structuur als die voldoet aan een bepaalde regelmaat. We bestuderen zowel een beschrijving van die regelmaat met woorden als een zeer precieze wetenschappelijke beschrijving. We laten dan telkens zien hoe we concrete recursieve structuren kunnen bouwen die aan zo’n beschrijving voldoen.

Voorstelling van Recursieve Structuren in Python

We hebben reeds besproken hoe we in Python tupels kunnen gebruiken om verschillende waarden te groeperen. Zo is (1,2,3,4) een groepering van 4 getallen en is (1,"hallo",2,True) een groepje waarden dat uit een getal, een string, nog een getal en een booleaanse waarde bestaat. We hebben ook gezien dat lijsten een alternatief vormen voor tupels. De keuze tussen tupels en lijsten zal afhangen van het feit of we de resulterende structuur nadien nog willen muteren of niet.

We hebben reeds aangehaald dat we tupels in tupels kunnen stoppen. Dit is perfect mogelijk aangezien een tupel een Python waarde is “als een ander”. Zo kunnen we bijvoorbeeld ((1,2),(3,4)) schrijven. Dit is een tupel dat 2 waarden groepeert die beide op hun beurt tupels zijn. Merk op dat dit niet hetzelfde is als (1,2,3,4). Dit laatste is immers een tupel dat gewoon uit 4 waarden bestaat. Tupels die tupels bevatten hebben we geneste tupels genoemd. Compleet analoog kunnen we lijsten willekeurig diep in mekaar nesten en kunnen we zelfs lijsten en tupels vrij met mekaar mixen in een geneste structuur. Alles hangt ervan af of we (een bepaald gedeelte van) de geneste structuur nadien nog willen wijzigen m.b.v. een assignment.

Tupels en lijsten nesten is dus een veel krachtiger idee dan het gewoon samenlijmen van gegevens: het organiseert die gegevens immers in een welbepaalde (boom)structuur. De boom bestaat uit “interne knopen” (dit zijn de tupels of lijsten die de boom vormen) en “bladeren” (dit zijn de andere Python waarden die op het dieptste niveau van de nesting zitten).

Bekijk de voorbeeld erfgenamenboom die getoond werd in de inleiding. Deze boom is een grafische weergave van een recursieve structuur in het familierecht. Sommige personen hebben geen, één, twee of drie erfgenamen. In Python kunnen we deze recursieve structuur als volgt zeer makkelijk voorstellen d.m.v. een geneste lijst (of d.m.v. een genest tupel):

familie = ["Piet", ["Clara", "Rudy",
                             "Marie",
                             ["Jan",
                              "Corneel",
                              ["Jos",
                               "John"]]],
                   ["Suzanne", ["Piere",
                                "Koen"],
                               ["Robert", "Mario"]]]

familie

['Piet',
 ['Clara', 'Rudy', 'Marie', ['Jan', 'Corneel', ['Jos', 'John']]],
 ['Suzanne', ['Piere', 'Koen'], ['Robert', 'Mario']]]

Beschrijving van Recursieve Structuren

Het verhaal eindigt hier echter niet. Op zich geeft Python ons de mogelijkheid om gelijk welke boomstructuur te bouwen. We kunnen dit als de kracht van Python beschouwen, maar tegelijk is het ook de zwakte. Je kan immers gelijk welke spaghetti aan tupels of lijsten bouwen en dat is uiteraard niet de bedoeling. Zo is volgende geneste lijst geen “geldige” familieboom:

[[[],["Jan", [3], "Piet"],["Joris"], "Corneel"]]

[[[], ['Jan', [3], 'Piet'], ['Joris'], 'Corneel']]

Het probleem met deze lijststructuur is dat er een getal in staat, dat er een lege lijst in voorkomt en dat er een lijst met een deellijst in

voorkomt (t.t.z. zonder de naam van een familielid). We hebben dus “regels” nodig die beschrijven welke dingen we in een genest tupel (of lijst) mogen steken om een “geldige” recursieve structuur te bouwen voor een bepaalde situatie. Voor onze familiebomen zou zo’n beschrijving als volgt kunnen luiden:

  • iedere string is een geldige familieboom (t.t.z. gewoon de naam van één persoon).

  • indien \(B_1\), \(B_2\), …, \(B_n\) familiebomen zijn en indien \(s\) een string is, dan is ook \([s,B_1,B_2,...,B_n]\) een familieboom.

Je kan nu controleren dat de geneste lijst die aan de variable familie is toegekend aan deze regels voldoet. Met zegt dat de lijst goed gevormd is. De lijst zelf en elke onderdeel ervan is ofwel een string ofwel een lijst die begint met een string gevolgd door een aantal deellijsten die op hun beurt goed gevorm zijn.

Verwerking van recursieve structuren

De regelmaat in de opbouw van recursieve structuur leidt tot een regelmaat in de functies waarmee je zulke structuren kan manipuleren en bewerken. Stel dat je wil controleren of een bepaalde naam in een gegeven familieboom voorkomt. De code is vrij simpel. De buitenste if maakt het onderscheid tussen de twee opties die we in de beschrijving van een familieboom hierboven gaven: ofwel is de boom gewoon 1 enkele naam ofwel is de boom een lijst met een naam voorop en een aantal deellijsten.

Controleren of de boom 1 enkele naam is gebeurt door te testen dat het type van wat we vasthebben str is. Is dat het geval dan wordt gecontroleerd of die naam gelijk is aan de naam die we zoeken en wordt overeenkomstig True of False teruggegeven. In het else deel van die buitenste if ben je daarna zeker dat je een lijst vasthebt die begint met een naam en dan deellijsten (omdat je er mag van uit gaan dat je familieboom goed gevormd is).

De geneste if gaat dan kijken of de naam die vooraan in de lijst staat toevallig de naam is die we zoeken en geeft in dat geval direct True terug. De else tak gaat dan d.m.v. een for recursief de functie find oproepen op alle deelbomen die verderop nog in die lijst staan. Zogauw in één van die deelbomen de naam gevonden wordt wordt er True teruggegeven. Als de naam in geen van die deelbomen wordt gevonden wordt uiteindelijk False teruggegeven.

def find(name, tree):
    if type(tree) == str:
        return tree == name
    else: 
        if tree[0] == name:
            return True
        else:
            for subtree in tree[1:]:
                if find(name,subtree):
                    return True
            return False

familie

['Piet',
 ['Clara', 'Rudy', 'Marie', ['Jan', 'Corneel', ['Jos', 'John']]],
 ['Suzanne', ['Piere', 'Koen'], ['Robert', 'Mario']]]

find('Piet', familie)

True

find('Marie', familie)

True

find('Jef', familie)

False

In wat volgt introduceren we twee gevalstudies. In de eerste gevalstudie (die komt uit de wiskunde) spitsen we onze aandacht toe op de voorstelling van een recursieve structuur en op de verwerking ervan m.b.v. recursieve Python functies. We zullen die recursieve structuur eerst gewoon in het Nederlands beschrijven en vervolgens met een passende representatie in Python uitwerken. In de tweede gevalstudie (die komt uit de biologie en met toepassingen in de wiskunde) bestuderen we de beschrijving van recursieve structuren op een heel precieze manier (namelijk zgn. Lindenmayer-systemen). We bestuderen dan opnieuw een voorstelling die past bij deze beschrijving en we bekijken opnieuw hoe we Python functies kunnen schrijven die op de structuur (in)werken.

Rekenkundige Uitdrukkingen

We hebben dus getoond dat er naast recursieve functies ook zoiets bestaat als recursieve structuren en dat we concrete voorbeelden van die recursieve structuren kunnen voorstellen als een boom. Bovendien kunnen we die bomen makkelijk voorstellen in Python als een reeks van correct geneste tupels of lijsten.

Laat ons eerst het eerder aangehaalde voorbeeld van de rekenkundige uitdrukkingen wat dieper onder de loep nemen. In wat volgt spitsen we ons toe op gewone binaire rekenkundige uitdrukkingen die ook één onbekende \(x\) mogen bevatten. Voorbeelden zijn \(x\), \(3\), \(2+2\), \(x+4\), \(x^2+3x+5\) en zo verder. De operatoren die we toelaten zijn de optelling \(+\), de vermenigvuldiging \(*\) en de machtsverheffing \(**\). Operatoren zoals \(-\) en \(/\) laten we weg omwille van de eenvoud maar het is een relatief gemakkelijke oefening om alles wat volgt ook voor deze operatoren toe te passen.

Merk op dat onze “gewone” manier om uitdrukkingen op te schrijven zonder haakjes eigenlijk een afkorting is. Zo is de uitdrukking \(x^2+3x+5\) eigenlijk een afkorting voor \((((x**2)+(3*x))+5)\) of \(((x**2)+((3*x)+5))\). We zijn er aan gewend de haakjes niet op te schrijven aangezien we voorrangsregels kennen en \(+\) toch een associatieve operator is. Maar strikt wiskundig en in het algemene geval moeten we die haakjes eigenlijk schrijven. Denk maar aan dezelfde uitdrukking met een \(-\) i.p.v. \(+\) en dan zien we meteen dat de positie van de haakjes er wel degelijk toe doet. Het punt dat we hier eigenlijk maken is dat de operatoren binaire operatoren zijn; ze nemen precies \(2\) argumenten. Vanaf nu zullen we dan ook heel precies zijn in ons gebruik van die operatoren en zullen we dus steeds de volledig gehaakte versie van iedere uitdrukking neerschrijven.

We kunnen rekenkundige uitdrukkingen dan in het algemeen beschrijven als alle structuren die we met de volgende regels kunnen bouwen. De eerste twee gevallen dienen om de atomaire structuren te bepalen. De derde (inductieve) regel bouwt de eigenlijke recursieve structuur:

  • ieder getal is een rekenkundige uitdrukking.

  • de variabele \(x\) is een rekenkundige uitdrukking.

  • als \(e_1\) en \(e_2\) rekenkundige uitdrukkingen zijn en als \(n\) een getal is, dan zijn ook \((e_1 + e_2)\), \((e_1 * e_2)\) en \((e_1~**~n)\) rekenkundige uitdrukkingen.

De uitdrukking die wij normaal als \(x^4+5x\) opschrijven wordt door deze definitie precies opgeschreven als \(((x~**~4)~+~(5~*~x))\) en de uitdrukking die we normaal als \(2(5x^2+3x)\) opschrijven, wordt dan \((2~*~((5~*~(x~**~2))+(3~*~x)))\).

Nadat we onze uitdrukkingen algemeen beschrijven op basis van binaire operatoren, kunnen we voor elke concrete uitdrukking een boom tekenen. De bladeren van de boom zijn atomair (in ons geval zijn dat de getallen of de variabele \(x\)). De knopen van de boom bestaan uit een operator met \(2\) vertakkingen naar deelbomen die overeenkomen met de deeluitdrukkingen die de operanden voorstellen. Bovenstaande voorbeelden zijn in boomvorm getekend in onderstaande figuur.

Zoals eerder vermeld, stellen we een boom voor in Python m.b.v. een genest tupel of een geneste lijst. Zo kunnen we bijvoorbeeld de uitdrukking \(x^4+5x\) (waarvan we de getekende boom terug vinden links in de figuur voorstellen als een genest tupel in Python. Dit doen we bijvoorbeeld als volgt:

test = (("x", "**", 4), "+" , (5, "*", "x"))

De variabele test is dan geassocieerd met een tupel dat uit drie componenten bestaat: een tupel, de string "+" en een tweede tupel. Beide geneste tupels bestaan op hun beurt ook uit 3 componenten: bewerking in het midden en 2 deeluitdrukkingen die in dit voorbeeld atomair zijn, i.e. ofwel een getal ofwel de string "x". Volgende interactie laat zien hoe we op de gewone manier toegang krijgen tot de componenten van dat tupel. De “linkertak” van de boom vinden we in component \(0\) en zijn “rechtertak” vinden we in component \(2\). De bewerking van een rekenkundige uitdrukking zit steeds in de middelste component van het corresponderende tupel en deze kunnen we opvragen in component \(1\).

test

(('x', '**', 4), '+', (5, '*', 'x'))

test[0]

('x', '**', 4)

test[1]

'+'

test[2]

(5, '*', 'x')

We gaan nu aantonen dat een pak interessante bewerkingen die we op rekenkundige uitdrukkingen kunnen doen (zoals “substitutie” of “afleiden”) heel elegant geformuleerd kunnen worden als een recursieve functie in Python.

Uitdrukkingen Uitrekenen

Beschouw bijvoorbeeld onderstaande Python functie:

def number(expr):
    return type(expr) == int 

def solve(expr, value):
    if number(expr): 
        return expr
    elif expr == "x":
        return value
    else:
        if expr[1] == "+":
            return solve(expr[0],value) + solve(expr[2],value)
        elif expr[1] == "*":
            return solve(expr[0],value) * solve(expr[2],value)
        elif expr[1] == "**":
            return solve(expr[0],value) ** expr[2]
        else: return None

De functie solve neemt 2 argumenten: een rekenkundige uitdrukking en een numerieke waarde. De uitdrukking is een genest tupel dat een rekenkundige uitdrukking voorstelt zoals hierboven werd beschreven. De waarde is een gewoon getal (t.t.z. een int of een float).

Wat doet solve? Alvorens in detail te treden geven we enkele gebruiksvoorbeelden. De bedoeling is dat de eerste parameter een rekenkundige uitdrukking voorstelt die een onafhankelijke "x" bevat en dat we dan die uitdrukking volledig gaan “uitrekenen” door alle voorkomens van "x" “in te vullen” met de waarde van de tweede parameter. solve wordt dus toegepast op een uitdrukking en een getal en levert steeds een getal op. Enkele voorbeelden volgen hieronder. test is een genest tupel dat overeenkomt met de uitdrukking \(x^4 + 5x\). solve(test,1) rekent dan \(1^4+5*1\) uit en solve(test,3) rekent \(3^4+5*3\) uit.

test = (("x", "**", 4), "+" , ("x", "*", 5))

test

(('x', '**', 4), '+', ('x', '*', 5))

solve(test,1)

6

solve(test,3)

96

Laat ons dan nu naar de code van solve kijken. Het is duidelijk een recursieve functie. Ze heeft twee stopcondities die in de eerste 2 takken van de if test verwerkt zitten. Die komen overeen met de eerste twee regels van de beschrijving van rekenkundige uitdrukkingen die we voorop stelden. De eerste stopconditie zorgt ervoor dat solve gewoon de expressie oplevert indien die expressie reeds een getal is. De tweede stopconditie zorgt ervoor dat solve de value weergeeft indien we een "x" tegenkomen als expressie.

Alle recursieve oproepen zitten in de derde en laatste tak verwerkt. Die komt overeen met de derde inductieve regel van de beschrijving. In de derde tak van de recursieve functie zien we een geneste if staan. Merk op dat we deze even goed hadden kunnen bijvoegen bij de buitenste if met wat extra elif’s. We hebben dit niet gedaan omwille van de leesbaarheid van de code: de stopcondities worden nu duidelijk afgezet tegen de tak met recursieve oproepen. Wat doen de recursieve aanroepen? De eerste drie takken van de geneste if test gaan kijken wat de bewerking is die op positie \(1\) staat in het tupel. Aangezien we zeker zijn dat de expressie geen getal is en geen "x" weten we dat het een tupel moet zijn (tenzij we solve natuurlijk toegepast hebben op een Python waarde die helemaal geen goed gevormde uitdrukking voorstelt!).

In het geval dat de uitdrukking een optelling voorstelt, roepen we recursief solve op op de linkertak en op de rechtertak van de uitdrukking. Nadien worden beide getallen effectief opgeteld met de Python + operator. Precies hetzelfde gebeurt er voor de uitdrukkingen die vermenigvuldigingen voorstellen. De tak van solve die met machtsverheffingen omgaat is een beetje speciaal. We zijn er tot nu toe stilzwijgend van uitgegaan dat de rechtertak van een machtsverheffing (t.t.z. de exponent) steeds een geheel getal is. We laten dus wel toe om uitdrukkingen als \(x^4\) voor te stellen maar expressies als \(x^{x+4}\) zijn verboden. De reden hiervoor zal straks duidelijk worden als we uitdrukkingen gaan afleiden. Het feit dat we weten dat de exponent steeds een getal is zien we in de elif tak die omgaat met de "**" operator: om de uitdrukking uit te rekenen gaan we recursief de linkertak uitrekenen en de waarde die hieruit voorkomt verheffen we tot de macht van de rechtertak; we gaan dus die rechtertak niet uitrekenen aangezien dit toch al een getal is.

In de allerlaatste tak van de geneste if test geven we None weer. Dit is niet strikt noodzakelijk: Python zou reeds automatisch deze waarde teruggeven als er voor een bepaalde invoer geen geldige elif met bijpassende return bestaat. Het is echter duidelijker om dit expliciet aan te geven zodat een lezer van onze code expliciet ziet dat we met mogelijke andere gevallen (zoals bijvoorbeeld aftrekkingen en delingen) geen rekening hebben gehouden.

Uitdrukkingen Afleiden

solve was een eerste voorbeeld van een (boom)recursieve functie die werkt op recursieve structuren: de uitdrukkingen die we als parameter meegeven zijn recursieve structuren en de recursie van solve volgt mooi de contouren van de recursie van de gegevens: de eindconditie in de recursieve functie correspondeert met de atomaire gevallen en de recursieve oproep van de functie gebeurt wanneer de invoergegevens effectief recursieve gegevens bevat.

Laat ons een tweede (overigens prachtig) voorbeeld bekijken van zo’n recursieve functie die werkt op onze recursieve rekenkundige uitdrukkingen. Iedereen herinnert zich wellicht nog hoe we in de wiskundeles functies in één variabele \(x\) afleiden. Voor de volledigheid herhalen we de regels voor afleiden (naar \(x\)) nog even:

\[\begin{split}\left. \begin{array}{l} c' =0 ~als~c~een~constante~ is \\ x' = 1 \\ (f+g)' = f'+g' \\ (f.g)' = f'.g+f.g' \\ (f^n)' = n.f'.(f^{n-1})' \end{array}\right.\end{split}\]

Deze regels kunnen we als volgt in Python neerschrijven:

def derive(expr):
    if number(expr):
        return 0
    elif expr == "x":
        return 1
    elif expr[1] == "+":
        return (derive(expr[0]), "+", derive(expr[2]))
    elif expr[1] == "*":
        return ((derive(expr[0]), "*", expr[2]),
                "+",
                ((expr[0]), "*", derive(expr[2])))
    elif expr[1] == "**":
        return (expr[2], "*", (derive(expr[0]), 
                               "*",  
                               (expr[0], "**", expr[2]-1)))
    else:
        return None

derive is een recursieve functie die een uitdrukking (een genest tupel dus) als invoer neemt en die een uitdrukking (opnieuw een genest tupel) als resultaat oplevert. De teruggegeven uitdrukking is de afgeleide van de invoer. De recursieve functie bevat een if test met 6 takken. Deze corresponderen met de 5 gevallen in onze definitie van afleiden, plus een extra else tak die netjes None weergeeft bij onvoorziene invoer.

derive heeft opnieuw 2 stopcondities: in het geval de invoeruitdrukking een getal is geven we 0 weer en in het geval de invoeruitdrukking "x" is geven we het getal 1 weer. Alle andere elif takken analyseren de invoeruitdrukking als een genest tupel door op positie \(1\) te kijken om te beslissen met welke operator we te maken hebben. Merk op dat in alle drie de gevallen een tupel teruggegeven wordt. Voor de optelling is het duidelijk: we geven een “optellingsuitdrukking” (t.t.z. een tupel waarvan de middelste component "+" is) waarbij we op positie \(0\) de afgeleide van de linkertak en op positie \(2\) de afgeleide van de rechtertak opnemen. Ook voor het afleiden van een vermenigvuldiging geven we een optellingsuitdrukking weer. In dit geval zijn beide componenten van die optelling echter vermenigvuldigingsuitdrukkingen. De eerste vermenigvuldiging bestaat uit de afgeleide van de linkertak en de originele rechtertak. Dit correspondeert met de \(f'.g\) in hogervermelde regels. De tweede vermenigvuldiging bestaat uit de originele linkertak en de afgeleide van de rechtertak. Dit correspondeert dan weer met de \(f.g'\) in die regel. We laten het ontcijferen van de machtsverheffing over aan de lezer. Belangrijk is in te zien hoe een reeks van twee vermenigvuldigingen (in de regels) voorgesteld worden door twee geneste tupels die elk op hun beurt vermenigvuldigingen voorstellen.

Hieronder illustreren we het gebruik van derive:

test = (("x", "**", 4), "+" , ("x", "*", 5))

test

(('x', '**', 4), '+', ('x', '*', 5))

derive(test)

((4, '*', (1, '*', ('x', '**', 3))), '+', ((1, '*', 5), '+', ('x', '*', 0)))

We bouwen eerst een uitdrukking test die de Python voorstelling van \(x^4+5x\) is. Het oproepen van derive(test) geeft dan de uitdrukking die de afgeleide van de invoeruitdrukking zou moeten voorstellen nml. \(((4* (1* x^3)))+((1*5)+(x*0)))\). Dat resultaat kunnen we m.b.v. een boom grafisch voorstellen zoals in onderstaande figuur.

Alhoewel het resultaat van derive(test) mathematisch correct is, zien we dat er een aantal vereenvoudigingen die wij mensen automatisch “opkuisen” door de functie derive niet doorgevoerd werden. Deze vereenvoudigingen hebben meestal te maken met vermenigvuldigen met \(0\) of \(1\), ergens \(0\) bij optellen, iets tot de nulde macht verheffen en \(1\) tot een bepaalde macht verheffen. Schematisch kunnen we de vereenvoudiging als volgt oplijsten:

\[\begin{split}\left. \begin{array}{l|l|l} optelling & vermenigvuldiging & machtsverheffing \\ \hline iets~+~0~ \rightarrow~iets & 0~*~iets~\rightarrow~0 & x^0~\rightarrow~1\\ 0~+iets~\rightarrow~iets & iets~*~0~\rightarrow~0 & 1^{iets}\rightarrow~1\\ & 1~*~iets~\rightarrow~iets & \\ & iets~*~1~\rightarrow~iets & \end{array}\right.\end{split}\]

Deze regels kunnen we integreren in onze afleidingsfunctie. De verbeterde functie derive ziet er als volgt uit:

def derive(expr):
    if number(expr):
        return 0
    elif expr == "x":
        return 1
    elif expr[1] == "+":
        return sum_expr(derive(expr[0]), derive(expr[2]))
    elif expr[1] == "*":
        return sum_expr(prod_expr(derive(expr[0]), expr[2]),
                        prod_expr(expr[0], derive(expr[2])))
    elif expr[1] == "**":
        return prod_expr(expr[2],
                        prod_expr(derive(expr[0]),
                            pow_expr(expr[0], expr[2]-1)))
    else:
        return None

De structuur van deze functie is helemaal dezelfde als die van de originele derive functie. Maar in plaats de resultaattupels ter plekke op te schrijven, roepen we de functies sum_expr, prod_expr en pow_expr aan. Deze drie functies zullen dan de nodige tupels opleveren maar zullen eventueel eerst een aantal van bovenstaande vereenvoudigingen toepassen. Als eerste voorbeeld bekijken we sum_expr.

def sum_expr(left, right):
    if number(left) and number(right): 
        return left+right
    elif left == 0: 
        return right
    elif right == 0: 
        return left
    else: 
        return (left, '+', right)

De bedoeling van deze functie is dat ze met gegeven bomen left en right een optellingsuitdrukking maakt en teruggeeft. Indien beide argumenten gewoon getallen zijn, geven we de numerieke som weer. Indien één van beide argumenten nul is, laten we die vallen en geven we gewoon de andere als resultaat weer. Alleen in het algemene geval (t.t.z. de else tak) geven we een nieuw tupel weer dat een optellingsuitdrukking voorstelt.

De functie die vermenigvuldigingen maakt ziet er gelijkaardig uit. Indien beide bomen getallen zijn, geven we het numerieke product weer. Indien één van beide bomen nul is, geven we het getal nul weer. Indien één van beide bomen \(1\) is laten we die vallen en geven we de andere weer. Het algemene geval bestaat uit het teruggeven van een verse vermenigvuldigingsboom d.m.v. een tupel.

def prod_expr(left, right):
    if number(left) and number(right): 
        return left*right
    elif left == 0 or right == 0: 
        return 0
    elif left == 1: 
        return right
    elif right == 1: 
        return left
    else: 
        return (left, '*', right)

Tenslotte bekijken we de functie pow_expr die machtsverheffingen maakt. Herinner dat we er hierbij van uitgaan dat de rechtertak steeds een geheel getal is (n genoemd in de functie hieronder). Indien de linkertak ook een getal is, rekenen we de macht meteen numeriek uit m.b.v. de Python ** operator. Indien de exponent \(0\) is, geven we \(1\) terug. Indien het grondtal \(1\) is, geven we \(1\) terug. In alle andere gevallen geven we een vers tupel terug dat een machtsverheffingsboom voorstelt.

def pow_expr(left,n):
    if number(left): 
        return left**n
    elif n == 0: 
        return 1
    elif left == 1: 
        return 1
    else: 
        return (left, '**', n)

Nu de drie hulpfuncties geschreven zijn kunnen we de nieuwe versie van derivetesten. Het resultaat is nu \(4x^3+5\) en dus inderdaad een stuk simpelder dan bij de eerste versie van derive en komt overeen met het resultaat dat je verwacht als je in de wiskundeoefeningen met de hand aan het afleiden gaat. Mathematisch zijn beide afgeleiden correct.

test = (("x", "**", 4), "+" , ("x", "*", 5))

test

(('x', '**', 4), '+', ('x', '*', 5))

derive(test)

((4, '*', ('x', '**', 3)), '+', 5)

Zowel sum_expr, prod_expr als pow_expr bevatten een subtiliteit die heel belangrijk is om te begrijpen. Bekijk bijvoorbeeld opnieuw sum_expr. Daarin zien we twee keer + staan. De eerste keer is dat de Python optellingsoperator die wordt toegepast op twee getallen. De tweede keer staat die + tussen aanhalingstekens en stelt het een string voor die in een tupel gebruikt wordt dat dat tupel een optellingsuitdrukking voorstelt. Dezelfde opmerking geldt voor * en ** in prod_expr en pow_expr respectievelijk.

In de praktijk

Het voorstellen van rekenkundige uitdrukkingen m.b.v. een boom en het verwerken van rekenkundige uitdrukkingen (bvb. afleiden of uitrekenen) m.b.v. een recursieve functies is wat diep binnenin programma’s als Excel gebeurt. Gebruikers kunnen in de invoerbalk formules intikken in de vorm van een string. Excel zal de formule van iedere cel voorstellen als een boom. Telkens de inhoud van een cel herberekend dient te worden zal de boom afgelopen worden op de manier die we hierboven beschreven hebben. Een ander voorbeeld wordt gevormd door wetenschappelijke rekenmachines die krachtig genoeg zijn om afgeleiden te berekenen. Ook hier kan de gebruiker functies gewoon intikken als string. Binnenin de machine zullen ze echter voorgesteld worden als een boom om volgens de hierboven beschreven techniek recursief afgeleid te kunnen worden.

Lindenmayer Systemen

In bovenstaande gevalstudie werd de beschrijving van alle geldige rekenkundige uitdrukkingen gewoon in het Nederlands gegeven. In de volgende gevalstudie behandelen we een zeer precieze manier om recursieve structuren te beschrijven. Dit is niet alleen meer wetenschappelijk. Het laat ook toe om Python functies te schrijven die concrete recursieve structuren genereren op basis van de beschrijving.

Simulatie van Algengroei

Lindenmayer-systemen werden in 1968 uitgevonden door de Hongaarse bioloog Aristid Lindenmayer (1925-1989) toen hij de groei van algen bestudeerde. Lindenmayer ontdekte dat de cellen van een bepaalde soort algen zich op ieder moment in twee verschillende toestanden kunnen bevinden: in de groeitoestand of in de voortplantingstoestand. Een cel die zich in groeitoestand bevindt zal uiteindelijk groeien tot de reproductietoestand. Een cel die zich in reproductietoestand bevindt zal zich splitsen in twee cellen waarvan de ene zich in groeitoestand bevindt en waarvan de andere zich in reproductietoestand bevindt. We refereren naar onderstaande figuur voor een plaatje.

image

Lindenmayer kon de uiteindelijke structuur van het alg voorspellen als volgt. Een cel die zich in reproductieve toestand bevindt noteerde hij met een \(A\) en een cel die zich in groeitoestand bevindt noteerde hij met een \(B\). De hierboven beschreven veranderingen noteerde hij met de volgende “regels”:

\[\begin{split}\begin{array}{l} A \rightarrow AB\\ B \rightarrow A\\ \end{array}\end{split}\]

Hiermee kunnen we vertrekken vanuit \(1\) enkele cel die zich in toestand \(A\) of \(B\) bevindt en vervolgens bestuderen tot welk resultaat de veranderingen uiteindelijk zullen leiden. Het is echter zeer makkelijk om hierin fouten te maken. Stel dat we vertrekken met een \(A\) en dat we deze volgens de regels laten evolueren in \(AB\). We kunnen dan zeggen dat de eerste \(A\) hiervan opnieuw kan evolueren tot een \(AB\) wat als tussenresultaat \(ABB\) oplevert. Indien we opnieuw deze redenering volgen krijgen we \(ABBB\). Vervolgens zouden we kunnen bedenken dat de laatste \(B\) hiervan volgens de regels verandert in een \(ABBA\). Enzovoort.

Wat we in deze redenering echter uit het oog hebben verloren is dat de cellen zich in de echte wereld niet één per één zullen transformeren maar wel allemaal tegelijk. De eerste stap van de redenering is nog steeds correct: we vertrekken van een \(A\) en krijgen volgens de eerste regel \(AB\). Maar dan moeten we echter juist redeneren en de \(A\) laten evolueren naar \(AB\) en tegelijkertijd de \(B\) laten evolueren naar een \(A\). Het resultaat van de tweede stap is dus \(ABA\). Ook nu dienen we opnieuw drie redeneringen tegelijkertijd te maken: de eerste \(A\) verandert in een \(AB\), de eerste \(B\) verandert in een \(A\) en de tweede \(A\) verandert in \(AB\). Het resultaat van de tweede verandering is dus \(ABAAB\).

De hele idee achter een Lindenmayer-systeem is dus dat het een verzameling van regels is samen met een beginvariabele van waaruit we m.b.v. de regels telkens een nieuwe reeks letters genereren door alle variabelen te vervangen door de rechterkant van de bijhorende regel. In ons voorbeeld hebben we twee regels en twee variabelen (namelijk \(A\) en \(B\)). In het algemeen bestaat een Lindenmayer-systeem uit:

  1. een verzameling variabelen

  2. een startvariabele

  3. een verzameling constanten

  4. een verzameling regels die vastlegt hoe een variabele wordt vervangen door een combinatie van variabelen en constanten

Voorlopig hebben we niet over constanten gesproken. Het Lindenmayer-systeem dat de algengroei simuleert heeft dan ook een lege verzameling constanten. De latere voorbeelden van Lindenmayer-systemen zullen wel constanten gebruiken.

Bovenstaande redenering — waarbij we de groei van een alg voorspellen door van \(A\) te vertrekken en dan telkens alle variabelen te vervangen door de rechterkant van de bijhorende regel— kunnen we grafisch weergeven zoals getoond in onderstaande figuur. De boom die we verkrijgen heeft \(A\) als top en vertoont vertakkingen voor alle variabelen die we aan de rechterkant van de regel zien staan. De eigenlijke alg lezen we van links naar rechts af aan de onderkant van de boom. In de figuur is dat \(ABAABABA\). Merk tenslotte op dat de lengte van een alg steeds een Fibonacci-getal is!

Lindenmayer-systemen in Python

De volgende code laat zien hoe we bovenstaand Lindenmayer-systeem kunnen voorstellen in Python.

algaevars   = ['A', 'B']
algaeconsts = []
algaerules  = [('A',['A','B']), ('B', ['A'])]
algaestart  = 'A'

We stellen de verzamelingen constanten en variabelen gewoon voor door lijsten. In dit geval is algaeconsts de lege lijst omdat we geen constanten hebben (zie hiervoor het volgende Lindenmayer-systeem). De regels zijn ook in een lijst ondergebracht. Iedere regel is voorgesteld door een 2-tupel. Zo wordt bij voorbeeld de regel \(A \rightarrow AB\) voorgesteld door het 2-tupel (’A’,[’A’,’B’]).

De volgende Python functies volstaan om een recursieve structuur te genereren op basis van het Lindenmayer-systeem en op basis van een gegeven \(n\) die de diepte weergeeft van de gevraagde recursieve structuur. De structuur uit bovenstaande figuur krijgen we door de expressie grow_tree(’A’, algaeconsts, algaerules, 4) te evalueren in de REPL.

def expand_var(var, rules):
    for r in rules:
        if r[0] == var:
            return r[1]
        
def grow_tree(start, consts, rules, n):
    if n == 0:
        return start
    elif start in consts:
        return start
    else:
        res = []
        for var_or_const in expand_var(start, rules):
            res = res + [grow_tree(var_or_const, consts, rules, n-1)]
        return [start] + res

grow_tree("A", algaeconsts, algaerules, 4)

['A',
 ['A', ['A', ['A', 'A', 'B'], ['B', 'A']], ['B', ['A', 'A', 'B']]],
 ['B', ['A', ['A', 'A', 'B'], ['B', 'A']]]]

grow_tree wordt recursief toegepast met een variabele of een constante (zie later) als eerste argument start. Constanten worden nooit verder uitgewerkt en worden dan ook meteen weer teruggegeven uit de functie. Ook indien \(n\) nul is geven we meteen de start parameter weer, zelfs indien die geen constante bevat. Een boom van diepte nul maken is immers triviaal. Indien start een variabele is en bovendien \(n \neq 0\), dan is het de bedoeling een boom te maken die bestaat uit die variabele (als knoop in de boom) tesamen met alle deelbomen die we krijgen door de juiste regel op die variabele toe te passen en recursief de bomen van diepte \(n-1\) te maken die vanuit die variabelen vertrekken. expand_var zoekt de juiste regel voor een gegeven variabele en geeft de rechterkant van die regel (t.t.z. r[1]) terug. growtree creërt dus een boom door ieder symbool uit de rechterkant van de regel te beschouwen met een for lus. Voor ieder symbool wordt grow_tree opgeroepen en wordt de resulterende boom opgenomen als deelboom in de res variabele. De boom op niveau \(n\) bestaat dus uit de variabele die we uitwerken, samen met alle deelbomen van niveau \(n-1\) die we krijgen op basis van de rechterkant van de toegepaste regel.

M.b.v. grow_tree kunnen we dus bomen maken . Indien we nu de alg zélf nodig hebben, dan moeten we de onderkant van de boom in een string zien te krijgen. Dit gebeurt in de functie show_algae. Deze recursieve functie is eigenlijk heel eenvoudig. Ze wordt toegepast op een recursieve structuur. Op ieder niveau in de recursie beginnen we met een verse lege string en plakken we hier alle resultaten aan die we krijgen door de deelbomen recursief te bezoeken. Op het einde van de recursie (helemaal onderaan de boom dus) wordt een variabele gewoon weergegeven. Het eigenlijke werk van deze functie gebeurt dus bij het terugkeren uit de recursie want pas dan zal + al de resultaatstrings aan elkaar plakken.

def show_algae(tree):
    if tree in algaevars:
        return tree
    else:
        algae = ''
        for i in range(1, len(tree)):
            algae = algae + show_algae(tree[i])
        return algae

show_algae(grow_tree('A', algaeconsts, algaerules, 4))

'ABAABABA'

Sierpinskidriehoeken

Om de rol van de constanten te begrijpen bestuderen we nog 2 andere Lindenmayer-systemen. Het volgende Lindenmayer-systeem wordt gebruikt om zogenaamde Sierpinskidriehoeken te genereren. Eigenlijk moeten we spreken over “de” Sierpinskidriehoek. Hij staat afgebeeld in de linkerkant van onderstaande figuur. De Sierpinskidriehoek is een voorbeeld van wat men een fractal noemt in de wiskunde. Fractalen zijn zogenoemde “zelfsimilaire” tekeningen. Dat zijn tekeningen die zichzelf bevatten op gelijk welk niveau van vergroten of verkleinen. We zouden dus kunnen zeggen dat de Sierpinskidriehoek zichzelf bevat tot in het oneindig diepe. Alhoewel je het niet op het eerste zicht zou zeggen is de Sierpinskidriehoek eigenlijk één continu lijnstuk dat heel de tijd geknakt wordt tijdens het tekenen. Het lijnstuk begint in de linkerbenedenhoek en eindigt in de rechterbenedenhoek.

Indien we de driehoek met een computer willen tekenen kunnen we uiteraard slechts een eindige diepte bereiken. Zoniet zouden we oneindig lang moeten tekenen. Een blik op de rechterkant van de figuur laat zien wat we hiermee bedoelen. De tekening laat 4 benaderingen zien van de Sierpinskidriehoek voor een verschillende diepte van “zelfbevatting” (t.t.z. voor \(n=2\), \(n=4\), \(n=6\) en \(n=8\)).

We zijn nu geïnteresseerd in, gegeven \(n\), een rij tekencommando’s die ons zullen toelaten om de benadering voor die bepaalde \(n\) op het scherm te tekenen. We willen dus een rij instructies van de vorm “teken een lijn”, “draai links af” en “draai rechts af”. We kunnen de tekening dan maken door de rij instructies af te lopen en uit te voeren op het scherm met één of andere Python teken-module. Om deze rij te genereren gebruiken we hetvolgende Lindenmayer-systeem:

  • Variabelen: \(A\) en \(B\)

  • Startvariabele: \(A\)

  • Constanten: \(+\) en \(-\)

  • Regels: $\(\begin{array}{l} A \rightarrow B-A-B\\ B \rightarrow A+B+A\\ \end{array}\)$

In deze regels betekenen zowel \(A\) als \(B\) “teken een lijn”. \(+\) betekent “draai links af met een hoek van \(60\) graden”. \(-\) betekent “draai rechts af met een hoek van \(60\) graden”. Het inzicht achter de opeenvolgende benaderingen is dat een lijn op niveau \(n\) bestaat uit drie lijntjes op niveau \(n+1\). Daarom hebben we “teken een lijn” voorgesteld door een variabele en niet door een constante. Het zorgt ervoor dat we die op het volgende niveau nog verder kunnen vervangen. Het feit dat we “draai naar links” of “draai naar rechts” doen vanaf een bepaald punt in het vlak blijft constant zelfs indien we de lijnen die die punten verbinden later nog gaan uitdiepen m.b.v. \(3\) andere lijnen. Daarom zijn \(+\) en \(-\) dus geen variabelen maar constanten. Merk ten slotte op dat we bij de opsplitsing van lijnen afwisselend naar links en naar rechts knakken. M.a.w. indien we op niveau \(n\) 3 opeenvolgende lijnen tekenen, dan zullen we op niveau \(n+1\) negen lijntjes tekenen, waarvan er \(3\) naar de ene kant geknakt zijn, \(3\) naar de andere kant geknakt zijn en ten slotte weer \(3\) langs de ene kant geknakt zijn. De richting van knakken in op niveau \(n+1\) is tegenovergesteld aan de richting van knakken op niveau \(n\). Indien we deze afwisseling niet zouden toepassen en telkens langs dezelfde kant zouden knakken zouden we eerder een zeshoek krijgen. Deze afwisseling verklaart waarom we twee variabelen nodig hebben \(A\) en \(B\).

Laten we een voorbeeld bekijken. We beginnen met \(A\) op niveau \(n=0\). De meest eenvoudige driehoek is dus gewoon een lijn. Op niveau \(n=1\) krijgen we dus \(B-A-B\). Nu krijgen we dus een lijn die uit drie lijnen bestaat. Die drie lijnen zullen in \(n=2\) opnieuw door drie lijnen worden vervangen. Dat geeft \(A+B+A-B-A-B+B-A-B\). Enzovoort. Net zoals bij de algengroei vertrekken we dus vanuit de startvariabele en genereren we een recursieve structuur (t.t.z. een boom). De onderkant van die boom is dan -van links naar rechts gelezen- de juiste reeks instructies om de driehoek te tekenen. De diepte van de boom correspondeert met de diepte van de gegenereerde Sierpinski-tekening.

Om de boom te genereren gebruiken we dezelfde machinerie die we net ontwikkeld hebben voor het algenvoorbeeld. Al wat we moeten doen is de functie grow_tree oproepen met het bovenvermelde Lindenmayer-systeem voor Sierpinskidriehoeken. Hier is het in Python-vorm:

spvars   = ['A', 'B']
spconsts = ['+', '-']
sprules  = [('A', ['B', '-', 'A', '-', 'B']), 
            ('B', ['A', '+', 'B', '+', 'A'])]
spstart  = 'A'

Als voorbeeld genereren we de boom voor \(n=2\):

grow_tree('A', spconsts, sprules, 2)

['A',
 ['B', 'A', '+', 'B', '+', 'A'],
 '-',
 ['A', 'B', '-', 'A', '-', 'B'],
 '-',
 ['B', 'A', '+', 'B', '+', 'A']]

Turtle Graphics

We zullen de eigenlijke tekening maken door gebruik te maken van zogenoemde turtle graphics. Turtle graphics is een tekentechniek die in de jaren 60 werd ontwikkeld in de context van de programmeertaal Logo. In Logo was het de bedoeling dat kinderen leren programmeren door het geven van instructies aan een schildpad die een pen vasthoudt (vooruit, links, rechts, …). Lijnen ontstaan dan op het scherm tengevolge van het bewegen van de schildpad. Er bestaat een module om met turtle graphics te werken in een notebook. Het gebruik van import ipyturtle volstaat om er gebruik van te kunnen maken. Het is in deze cursus niet de bedoeling om alle functies uit deze module te gaan bestuderen. Deze informatie is trouwens makkelijk terug te vinden in de internetdocumentatie van Python.

De volgende code laat zien hoe we een simpel rood vierkant kunnen tekenen in een notebook. Eerst wordt van de module ipyturtle de klasse Turtle geïmporteerd en wordt er een instantie van gemaakt. Dat object is een schiuldpad en wordt door de REPL getoond in een venster met de gekozen grootte (breedte en hoogte in pixels uitgedrukt). Je ziet dat de nieuw gecreëerde schildpad naar boven gepositioneerd staat in het centrum van het venster.

from ipyturtle import Turtle

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
<ipython-input-37-6761862fcf84> in <module>
----> 1 from ipyturtle import Turtle

ModuleNotFoundError: No module named 'ipyturtle'

test = Turtle(fixed=False, width=400, height=300)

test

Het vierkant onstaat door de schildpad vier keer te laten vooruit lopen en een hoek van 90 graden naar links te draaien. De kleur van de lijn die getekend wordt kan je kiezen door de penkleur in te stellen. Merk op dat alles getekend wordt in het venster dat hiervoor net gecreëerd werd om de schildpad te tonen.

test.pencolor("red")
for i in range(0,4):
    test.forward(100)
    test.left(90)

Je kan test.reset() oproepen op de schidpad en alle tot nu toe getekende lijnen zullen verdwijnen van het venster. De schildpad zelf blijft bestaan. Dat is nuttig als je verschillende experimenten wil doen in hetzelfde venster.

De volgende functie zal een Sierpinskidriehoek tekenen met een gegeven turtle op op basis van een gegenereerde boom die in de parameter tree wordt meegegeven. De derde parameter size bepaalt de lengte van het lijnstukje dat wordt getekend en controleert dus de grootte van de hele figuur.

def draw_sierpinkski(tree,turtle,size):
    if tree == 'A' or tree == 'B':
        turtle.forward(size)
    elif tree == '+':
        turtle.right(60)
    elif tree == '-':
        turtle.left(60)
    else:
        for i in range(1, len(tree)):
            draw_sierpinkski(tree[i],turtle,size/2)

De functie neemt een boom en onderzoekt of die bestaat uit een \(A\), \(B\), \(-\) of \(+\). Indien dit niet het geval is, hebben we te maken met een lijst die deelbomen bevat. Deze lopen we gewoon van links naar rechts af. We passen draw_sierpinski toe op iedere deelboom. Er gebeurt dus niets zichtbaar terwijl we de boom naar beneden aflopen. Enkel op het allerlaatste niveau (t.t.z. bij de bladeren) zal er iets getekend worden. Iedere \(A\) of \(B\) geeft aanleiding tot een lijntje. Dat doen we d.m.v. de oproep turtle.forward(size). De size wordt op elke niveau van de recursie gehalveerd zodat de resulterende figuur de gevraagde grootte heeft. Iedere \(+\) doet de turtle \(60\) graden naar rechts draaien (zonder iets te tekenen) en iedere \(-\) doet de turtle \(60\) graden naar links draaien. Dat is alles!

Hieronder zetten we een testschildpad klaar met een blauwe pen en tekenen we een boom van diepte 3.

Je kan nu zelf experimenteren door ook eens de bomen met andere dieptes te tekenen. Vergeet niet van de lijnen van het vorige experiment te doen verdwijnen door reset op te roepen of creëer voor elk experiment een nieuwe schildpad.

sturtle = Turtle(fixed=False, width=400, height=300)
sturtle.pencolor("blue")

sturtle

draw_sierpinkski(grow_tree('A', spconsts, sprules, 4),sturtle,120)

De groei van fractale planten

Het derde Lindenmayer-systeem dat we bestuderen dient om de groeivertakking van hogere planten te bestuderen. We kunnen er tekeningen mee genereren zoals getoond in onderstaande figuur. Op zeer verrassende wijze zijn sommige planten eigenlijk recursieve structuren.

image

Het Lindenmayer-systeem om de groei van de plant in bovenstaande figuur te simuleren ziet er als volgt uit:

  • Variabelen: \(X\) en \(F\)

  • Startvariabele: \(X\)

  • Constanten: \(+\), \(-\), \(<\) en \(>\)

  • Regels: $\(\begin{array}{l} X \rightarrow F-<<X>+X>+F<+FX>-X\\ F \rightarrow FF\\ \end{array}\)$

Het systeem heeft twee variabelen \(F\) en \(X\). We vertrekken vanuit \(X\) en we zien uit de regels dat deze \(X\) vervangen kan worden door een vrij ingewikkelde rechterkant. Vanuit die rechterkant kunnen er opnieuw een aantal \(X\)’en uitgewerkt worden alsook een aantal \(F\)’en. Uit de regels zien we echter dat een \(F\) enkel kan leiden tot twee \(F\)’en en nooit nog aanleiding kan geven tot een \(X\). We kunnen experimenteren met verschillende vormen van complexiteit door deze regels eventueel te veranderen.

Indien we naar de tekening van de plant kijken zien we een nieuw fenomeen in vergelijking met de Sierpinskidriehoeken: de plant is niet langer 1 continue lijn maar wel een lijn met verschillende vertakkingen. Dit betekent dat onze schildpad 1 vertakking zal “afslaan” en ooit later op hetzelfde punt zal moeten terug staan om de andere vertakkingen verder te tekenen. De instructies om te tekenen bestaan daarom niet alleen uit “teken een lijn”, “sla links af” en “sla rechts af”, maar ook uit “onthou je positie” en “kom terug naar de onthouden positie”. Deze laatste twee instructies stellen we voor door de constanten \(<\) en \(>\).

Ook dit keer hergebruiken we onze reeds eerder geschreven code. De recursieve structuur voor een gegeven \(n\) kunnen we dus genereren door onze functie grow_tree op te roepen met de volgende Python voorstelling van bovenstaand Lindenmayer-systeem:

plantvars   = ['X', 'F']
plantconsts = ['+', '-', '<', '>']
plantrules  = [('X', ['F','-', '<', '<', 'X', '>','+', 'X', '>', 
                '+', 'F', '<', '+', 'F', 'X', '>', '-', 'X']),
                ('F', ['F', 'F'])]
plantstart = 'X'

Als voorbeeld genereren we een plant van diepte 2. Dit geeft reeds vrij veel teken-instructies:

grow_tree('X', plantconsts, plantrules, 2)

Net zoals voor de Sierpinskidriehoeken rest ons nu nog om een functie te schrijven die de instructies “afspeelt” en de bijhorende functies oproept om een schildpad het tekenwerk te laten doen. draw_plant neemt een boom en loopt die recursief helemaal af naar beneden toe. M.b.v. een for-lus wordt iedere deelboom recursief bezocht. Op het allerlaagste niveau (t.t.z. bij de bladeren van de boom) zien we voorkomens van \(F\), \(+\), \(-\), \(X\), \(<\) en \(>\). De constante \(F\) vertaalt naar een lijnstukje tekenen, \(+\) en \(-\) vertalen naar links of rechts draaien. De lengte van de lijnstukjes en de hoeken zijn hier vastgekozen. Je kan daar mee spelen en de vorm van de plant zal veranderen.

def draw_plant(tree,turtle):
    if tree == 'F':
        turtle.forward(8)
    elif tree == '+':
        turtle.right(24)
    elif tree == '-':
        turtle.left(24)
    elif tree == 'X':
         None
    elif tree == '<':
        store(turtle)
    elif tree == '>':
        restore(turtle)
    else:
        for i in range(1, len(tree)):
            draw_plant(tree[i],turtle)

De structuur van deze functie is zeer gelijklopend aan de functie draw_sierpinski. Het enige verschil is dat ze naast het tekenwerk en het links en rechts afslaan ook nog store() oproept om de huidige positie en looprichting van de schildpad op te slaan voor later gebruik. Dit gebeurt telkens we een ’<’ tegenkomen in de boom. Telkens we een een overeenkomende ’>’ zien herstellen we de positie en de looprichting van de schildpad naar de eerder opgeslagen positie door restore() aan te roepen. Daarbij wordt de pen van de schildpad eventjes ‘opgetrokken’ zodat er geen lijntje wordt getekend. Merk op dat er in de onderkant van de boom -indien van links naar rechts gelezen- meerdere ’<’ zullen voorkomen alvorens we de eerste ’>’ zien. store() moet dus meerdere posities kunnen onthouden en restore() moet telkens de meest recent onthouden positie het eerst herstellen. We laten het begrijpen van store() en restore() over aan de geïnteresseerde student:

memory = []

def store(turtle):
    global memory
    memory = [(turtle.position(),turtle.heading())] + memory
        
def restore(turtle):
    global memory
    ((x,y),h) = memory[0]
    memory= memory[1:]
    turtle.penup()
    turtle._turtle_location_x=x
    turtle._turtle_location_y=y
    turtle._turtle_heading=h
    turtle.pendown()

Het experiment hieronder ontwikkeld een boom van diepte 4 en tekent de overeenkomstige plant in het groen. De schildpad wordt onderaan in het midden van het venster gepositioneerd voor het tekenwerk start. Als je wil experimenteren met andere dieptes en met andere vormen van planten moet je ook de grootte van het tekenvenster eventueel aanpassen om de hele plant er in te krijgen.

pturtle = Turtle(fixed=False, width=400, height=360)
pturtle.pencolor("green")
pturtle._turtle_location_y=-180

pturtle

draw_plant(grow_tree('X', plantconsts, plantrules, 4),pturtle)

Rekenkundige Uitdrukkingen (vervolg)

Eigenlijk kunnen we de beschrijving van rekenkundige uitdrukkingen (die we in gewoon Nederlands deden) ook preciezeren m.b.v. een gepast Lindenmayer-systeem. Het ziet er als volgt uit:

  • Variabelen: \(E\) en \(I\) en \(V\)

  • Startvariabele: \(E\)

  • Constanten: \(+\), \(*\), \(**\),\(x\),\(0\), \(1\), \(2\), …

  • Regels: $\(\begin{array}{l} E \rightarrow I\\ E \rightarrow V\\ E \rightarrow E+E\\ E \rightarrow E*E\\ E \rightarrow E**I\\ I \rightarrow 1, 2, 3, ...\\ V \rightarrow x\\ \end{array}\)$

Uiteraard heeft het geen zin om rekenkundige uitdrukkingen te gaan genereren met grow_tree. Het zijn immers wij mensen die met de hand een “nuttige” rekenkundige uitdrukking bouwen indien één of andere wiskundige situatie zich aandient. Desalnietemin voldoet gelijk welke rekenkundige uitdrukking die we hierboven manipuleerden exact aan de beschrijving van bovenstaand Lindenmayer-systeem. Dat systeem vormt dus een precieze beschrijving van de verzameling van alle mogelijke ‘goed-gevormde’ rekenkundige uitdrukkingen.

In de praktijk

De kans is zeer reëel dat je ooit met een recursieve structuur te maken krijgt en dat je misschien zelfs een (Python) functie zal moeten schrijven om met die recursieve structuur iets te doen. Een zeer populaire technologie vandaag is XML. Dit is een (vrij ingewikkelde) taal waarin men recursieve structuren kan beschrijven voor allerlei (wetenschappelijke) toepassingen. Het wemelt op internet van de technologie om zulke XML-gebaseerde recursieve structuren te verwerken.

Het onderstaande voorbeeldje (dat we van Wikipedia gehaald hebben) is 1 recursieve structuur die werd opgeschreven in de zogenoemde Chemical Markup Language (CML) die op XML gebaseerd is. Het laat een boom zien die informatie over de molecule “carotine” voorstelt (die bestaat uit verschillende atomen). Uiteraard moet ook in CML iedere recursieve structuur voldoen aan een bepaalde beschrijving. Dit is een Lindenmayer-achtige beschrijving die in het voorbeeld met cml_schema wordt aangegeven. Het refereert naar een verzameling regels (die je op internet kan vinden) die de structuur beschrijven. De exacte details hiervan vallen buiten het bestek van de cursus.

Samenvatting

In dit topic hebben we onze kennis over recursie verder uitgewerkt. In dit deel hebben we recursieve structuren, oftewel bomen, bestudeerd. Die ontstaan wanneer we tupels (of lijsten) gaan nesten. Dit is de voorstelling van een recursieve structuur. Naast de voorstelling hebben we gezien hoe we Lindenmayer-systemen kunnen gebruiken om recursieve structuren te beschrijven. In vele gevallen kunnen we, gegeven een \(n\), een recursieve structuur laten genereren op basis van zo’n beschrijving. Voorbeelden hiervan waren de algen, de Sierpinskidriehoeken en de fractale planten. We kunnen dus Python functies schrijven die recursieve structuren als return waarde opleveren. Ook derive was een voorbeeld van zo’n functie.

De recursieve functies zoals fac en fib uit de topic over recursievefuncties werkten in eerste instantie op getallen. De recursieve functies smallest en average uit de topic over lijsten werken dan weer op gewone lijsten. In dit topic hebben we talloze voorbeelden gezien van functies die een recursieve structuur als invoer nemen en deze recursieve structuur op recursieve wijze aflopen. Voorbeelden hiervan waren show_algae, draw_sierpinski en draw_plant. Ook solve voor rekenkundige uitdrukkingen was een voorbeeld van een Python functie die een recursieve structuur afloopt.

TOPIC 6: Numerieke Benaderingen TOPIC 8: Objectgericht Programmeren - Deel 1: Objecten Gebruiken