Wat is recursie?De body (= het deel tussen ‘to functienaam’ en ‘end’) van een procedure bevat een opeenvolging van 2 soorten opdrachten :
Primitieve commando’s uit de taal (fd, bk, lt, rt...)
Zelf geschreven commando’s (procedures)
Een recursieve procedure zal een oproep naar zichzelf in zijn ‘body’ hebben.
Recursie in het echte leven : het ‘tv-in-tv effect’
Inleiding tot recursie Karel Popelier
Wat is recursie?
De body (= het deel tussen ‘to functienaam’ en ‘end’) van een procedure bevat een opeenvolging van 2 soorten opdrachten :
Primitieve commando’s uit de taal (fd, bk, lt, rt...)
Zelf geschreven commando’s (procedures)
Een recursieve procedure zal een oproep naar zichzelf in zijn ‘body’ hebben.
Recursie in het echte leven : het ‘tv-in-tv effect’
Een voorbeeld van recursie
Wat doet deze procedure ?
to functie :GETAL pr :GETAL functie :GETAL + 1 end
Let op : recursieve procedures kunnen leiden tot oneindige lussen.
We kunnen oneindige lussen vermijden door een stopconditie ahv een if-statement.
Een voorbeeld van recursie (2)
Wat is het verschil in resultaat tussen deze 2 functies? De 2 functies hebben een verschillend resultaat!
Verklaring: Wanneer de procedure zichzelf aanroept, bestaat er tegelijkertijd meer dan 1 uitvoering van die procedure. to telaf1 :GETAL if :GETAL < 1 [STOP] pr :GETAL telaf1 :GETAL – 1 end to telaf2 :GETAL if :GETAL < 1 [STOP] telaf2 :GETAL – 1 pr :GETAL end
Hoe werkt recursie? (telaf1 2)
end to telaf1 0 if 0 < 1 [STOP] end end Hier hebben we 3 simultane uitvoeringen. Resultaat : 2 1 to telaf1 2 if : 2 < 1 [STOP] pr 2 telaf1 1 to telaf1 1 if : 1 < 1 [STOP] pr 1 telaf1 0
Hoe werkt recursie? (telaf2 2)
pr 2 end to telaf2 0 if 0 < 1 [STOP] end pr 1 end Resultaat : 1 2 to telaf2 2 if : 2 < 1 [STOP] telaf2 1
to telaf2 1 if : 1 < 1 [STOP] telaf1 0
Conclusies
De plaats waar de recursieve aanroep staat, is belangrijk en kan een invloed hebben op het resultaat.
In het geval dat de recursieve aanroep als laatste instructie in de ‘body’ staat, kan in simpele gevallen het effect van de recursieve procedure ook met een lus (repeat, for) bekomen worden.
Hoe zou je telaf als lus schrijven?
Conclusie (2)
Het gebruik van recursie kan leiden tot korte, elegante procedures, maar het ontwerpen/ testen van recursieve procedures is niet altijd even evident en/of makkelijk.
Recursie kan gebruikt worden voor ingenieuze en gecompliceerde tekeningen te bekomen in de schildpadwereld(fractalen), maar zal ook in andere werelden toepassing vinden (bv. manipuleren van lijsten in de taalwereld)
Comments