Julekuler, snøflak og rekursjon

Julekuler, snøflak og rekursjon#

Obs

Denne guiden er litt avansert og krever at du har litt forkunnskaper om funksjoner i Python fra før.

Bildet under viser et eksempel av mønstrene vi kan lage ved å bruke fraktaler og skilpaddeprogrammering.

Et bilde av det ferdigbroderte snøfnugget.

Ser vi nærmere på «armene» til et snøfnugg, kan vi se at det ser ut til å bestå av mindre «armer». Når et mønster ser ut til å bestå av mindre kopier av seg selv kaller vi det et «fraktalt» mønster.

../_images/SIA-SIA2013-09119.png

Fraktalt snøflak#

Et snøflak hvor hver gren av hver arm har nye avgreninger (Bilde av Wilson Alwyn Bentley (1865-1931)).

Fraktale mønstre dukker opp mange steder i naturen og kunst

../_images/3104423642_31665c5fe4_c.jpg

Fraktal blomkål#

En blomkål hvor hver blomst ser ut som en liten blomkål (Bilde av Amber Case (CC-BY-NC)).

../_images/pexels-jeremy-bishop-14061015.jpg

Fraktal tre#

Grenene til et tre ser ut som et lite tre, og er derfor fraktalt (Bilde av Jeremy Bishop).

../_images/5419811742_9068550c29_c.jpg

Matematisk fraktal#

En visualisering av en fraktal Julia mengde (Bilde av Dominic Alves).

../_images/Kandariya_mahadeva_temple.jpg

Kandariya Mahadeva Tempelet#

Ett bilde av Kandariya Mahadeva tempelet som er konstruert som en tredimensjonal fraktal (Bilde av brukeren Antorjal på Wikipedia).

Vi kan tegne fraktale mønstre med kode ved hjelp av rekursive funksjoner. En rekursiv funksjon er en funksjon som kaller på seg selv. Så det vi må gjøre er å lage en funksjon som tegner en arm som består av mindre armer som tegnes av den samme funksjonen. Dette høres kanskje litt forvirrende ut, så la oss starte ved å lage en enkel tegn_arm funksjon som tegner en enkel arm.

 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde):
 4    # Gå litt frem
 5    nål.forward(0.4*lengde)
 6
 7    # Tegn første "gren", denne peker litt nedover
 8    nål.right(45)
 9    nål.forward(lengde*0.3)
10    nål.backward(lengde*0.3)
11    nål.left(45)
12    # Tegn andre "gren", denne peker litt oppover
13    nål.left(45)
14    nål.forward(lengde*0.3)
15    nål.backward(lengde*0.3)
16    nål.right(45)
17
18    # Gå litt fremover
19    nål.forward(lengde*0.6)
20
21nål = Turtle()
22with nål.running_stitch(30):
23    tegn_arm(nål, 200)
24
25nål.visualise()
En arm av et snøfnugg. En rett strek med to grener, en som peker oppover og en som peker nedover.

Hvis vi kaller på denne funksjonen, så får vi en arm, og vi ser at denne armen består av fire «biter», hvor hver del er et linjestykke hvor nåla beveger seg fremover. Det vi ønsker, er at hver slik bit skal bestå av en liten arm med to grener. For å oppnå det kan vi bytte ut kallet på forward-funksjonen med et kall på tegn_arm-funksjonen. Da får vi en funksjon som kaller på seg selv, også kjent som en rekursiv funksjon.

Bilde av en ordbok slått opp på ordet "rekursjon". Definisjonen er: "Se definisjon for rekursjon".
 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde):
 4    # Gå litt frem
 5    tegn_arm(nål, 0.4*lengde)
 6
 7    # Tegn første "gren", denne peker litt nedover
 8    nål.right(45)
 9    tegn_arm(nål, lengde*0.3)
10    nål.backward(lengde*0.3)
11    nål.left(45)
12    # Tegn andre "gren", denne peker litt oppover
13    nål.left(45)
14    tegn_arm(nål, lengde*0.3)
15    nål.backward(lengde*0.3)
16    nål.right(45)
17
18    # Gå litt fremover
19    tegn_arm(nål, lengde*0.6)
20
21nål = Turtle()
22with nål.running_stitch(30):
23    tegn_arm(nål, 200)
24
25nål.visualise()

Kjører vi denne koden vil den aldri bli ferdig å tegne siden hver gren vil bestå av en arm med grener hvor hver gren består av en arm med grener hvor hver gren… osv. Det blir uendelig mange detaljer – det klarer dessverre ikke datamaskinen håndtere, og vil derfor avslutte programmet med en RecursionError.

For å passe på at koden tegner ferdig til slutt, vi ha en variabel som passer på hvilket «rekursjonsnivå» vi er på. Da kan vi passe på at vi stopper etter en viss mengde nivåer:

 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(45)
12        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
13        nål.backward(lengde*0.3)
14        nål.left(45)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(45)
17        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
18        nål.backward(lengde*0.3)
19        nål.right(45)
20
21        # Gå litt fremover
22        tegn_arm(nål, lengde*0.6, rekursjonsnivå-1)
23
24nål = Turtle()
25with nål.running_stitch(30):
26    tegn_arm(nål, 200, 2)
27
28nål.visualise()
En arm av et snøfnugg. Det likner på snøfnugg-arm-figuren over, men hver rette strek fra figuren over er byttet ut med en liten arm.
Linje 3:

Her har vi lagt inn en inputvariabel, rekursjonsnivå som holder orden på hvilket «nivå» av rekursjon vi er på

Linje 4-5:

Her sjekker vi om vi har nådd nivå 0. I så fall skal vi tegne kun en enkel strek og ikke noen grener. Dette passer på at koden ikke kjører for alltid

Linje 8, 12, 17 og 22:

Når vi kaller på tegn_arm funksjonen inne i tegn_arm funksjonen sender vi inn rekursjonsnivå-1 for å indikere at vi har brukt opp et nivå av rekursjon. Dette gjør at vi kan holde orden på hvor mange nivåer vi har.

Linje 26:

Når vi bruker tegn_arm funksjonen utenfor funksjonen for å tegne en arm spesifiserer vi hvor mange rekursjonsnivåer vi ønsker.

Under er noen eksempler av hvordan armen blir å se ut for forskjellige rekursjonsnivåer:

Rekursjonsnivå 0

En rett strek
Kode:
 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(45)
12        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
13        nål.backward(lengde*0.3)
14        nål.left(45)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(45)
17        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
18        nål.backward(lengde*0.3)
19        nål.right(45)
20
21        # Gå litt fremover
22        tegn_arm(nål, lengde*0.6, rekursjonsnivå-1)
23
24nål = Turtle()
25with nål.running_stitch(30):
26    tegn_arm(nål, 200, 0)
27
28nål.visualise()

Rekursjonsnivå 1

Den samme snøflak-armen som ble tegnet i første kodeeksempel.
Kode:
 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(45)
12        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
13        nål.backward(lengde*0.3)
14        nål.left(45)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(45)
17        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
18        nål.backward(lengde*0.3)
19        nål.right(45)
20
21        # Gå litt fremover
22        tegn_arm(nål, lengde*0.6, rekursjonsnivå-1)
23
24nål = Turtle()
25with nål.running_stitch(30):
26    tegn_arm(nål, 200, 1)
27
28nål.visualise()

Rekursjonsnivå 2

En arm av et snøfnugg. Det likner på snøfnugg-arm-figuren over, men hver rette strek fra figuren over er byttet ut med en liten arm.
Kode:
 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(45)
12        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
13        nål.backward(lengde*0.3)
14        nål.left(45)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(45)
17        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
18        nål.backward(lengde*0.3)
19        nål.right(45)
20
21        # Gå litt fremover
22        tegn_arm(nål, lengde*0.6, rekursjonsnivå-1)
23
24nål = Turtle()
25with nål.running_stitch(30):
26    tegn_arm(nål, 200, 2)
27
28nål.visualise()

Prøv selv:

  • Oppdater koden til å tegne armer med rekursjonsnivå 3 og 4.

Klikk her for å se snøfnugg-armen og koden for rekursjonsnivå 3:En arm av et snøfnugg. Det likner på snøfnugg-arm-figuren over, men hver rette strek fra figuren over er byttet ut med en liten arm. Denne prosessen er gjentatt to ganger.
 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(45)
12        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
13        nål.backward(lengde*0.3)
14        nål.left(45)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(45)
17        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
18        nål.backward(lengde*0.3)
19        nål.right(45)
20
21        # Gå litt fremover
22        tegn_arm(nål, lengde*0.6, rekursjonsnivå-1)
23
24nål = Turtle()
25with nål.running_stitch(30):
26    tegn_arm(nål, 200, 3)
27
28nål.visualise()
Klikk her for å se snøfnugg-armen og koden for rekursjonsnivå 4:En arm av et snøfnugg. Det likner på snøfnugg-arm-figuren over, men hver rette strek fra figuren over er byttet ut med en liten arm. Denne prosessen er gjentatt tre ganger.
 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(45)
12        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
13        nål.backward(lengde*0.3)
14        nål.left(45)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(45)
17        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
18        nål.backward(lengde*0.3)
19        nål.right(45)
20
21        # Gå litt fremover
22        tegn_arm(nål, lengde*0.6, rekursjonsnivå-1)
23
24nål = Turtle()
25with nål.running_stitch(30):
26    tegn_arm(nål, 200, 4)
27
28nål.visualise()

Nå som vi har kode for å tegne en snøfnuggarm kan vi bruke repetisjon til å tegne et fullstendig snøfnugg:

 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(45)
12        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
13        nål.backward(lengde*0.3)
14        nål.left(45)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(45)
17        tegn_arm(nål, lengde*0.3, rekursjonsnivå-1)
18        nål.backward(lengde*0.3)
19        nål.right(45)
20
21        # Gå litt fremover
22        tegn_arm(nål, lengde*0.6, rekursjonsnivå-1)
23
24nål = Turtle()
25with nål.running_stitch(30):
26    for arm in range(6):
27        tegn_arm(nål, 200, 2)
28        nål.backward(200)
29        nål.right(60)
30
31nål.visualise()
Et snøflak hvor hver arm har rekursjonsdybde 2.

Prøv selv:

  • Kjør programmet og se hva du får ut

  • Endre slik at grenene har en annen vinkel (f.eks. 60 grader).

  • Endre slik at hver arm har to sett med grener. Nedenfor er en visualisering av hvordan det kan se ut.

En arm av et snøfnugg som har to sett med grener.
Klikk her for å se programmet slik det kan være om du har gjort det rett:
 1from turtlethread import Turtle
 2
 3def tegn_arm(nål, lengde, rekursjonsnivå):
 4    if rekursjonsnivå == 0:
 5        nål.forward(lengde)
 6    else:
 7        # Gå litt frem
 8        tegn_arm(nål, 0.4*lengde, rekursjonsnivå-1)
 9
10        # Tegn første "gren", denne peker litt nedover
11        nål.right(60)
12        tegn_arm(nål, lengde*0.2, rekursjonsnivå-1)
13        nål.backward(lengde*0.2)
14        nål.left(60)
15        # Tegn andre "gren", denne peker litt oppover
16        nål.left(60)
17        tegn_arm(nål, lengde*0.2, rekursjonsnivå-1)
18        nål.backward(lengde*0.2)
19        nål.right(60)
20        
21        tegn_arm(nål, 0.2*lengde, rekursjonsnivå-1)
22
23        # Tegn tredje "gren", denne peker litt nedover
24        nål.right(60)
25        tegn_arm(nål, lengde*0.2, rekursjonsnivå-1)
26        nål.backward(lengde*0.2)
27        nål.left(60)
28        # Tegn fjerde "gren", denne peker litt oppover
29        nål.left(60)
30        tegn_arm(nål, lengde*0.2, rekursjonsnivå-1)
31        nål.backward(lengde*0.2)
32        nål.right(60)
33
34        # Gå litt fremover
35        tegn_arm(nål, lengde*0.4, rekursjonsnivå-1)
36
37nål = Turtle()
38with nål.running_stitch(30):
39    for arm in range(6):
40        tegn_arm(nål, 200, 2)
41        nål.backward(200)
42        nål.right(60)
43
44nål.visualise()
Et bilde av broderimaskinen mens den lager et fraktalt snøfnugg.

Eksempelfraktaler#

Prøv selv:

  • Lag din egen fraktal! Under er et galleri med eksempler for inspirasjon

Eksempelfraktal 1

Et annet type fraktalt snøflak kalt "Koch-snøflaket". Et annet type fraktalt snøflak kalt "Koch-snøflaket".

Eksempelfraktal 2

Et fraktalt tre. Et fraktalt tre.

Eksempelfraktal 3

Et fraktalt snøflak med to forskjellige arm-typer, et for partals-rekursjonsnivå og ett for oddetalls rekursjonsnivå. Et fraktalt snøflak med to forskjellige arm-typer, et for partals-rekursjonsnivå og ett for oddetalls rekursjonsnivå.