Rekursiv algoritme
- rekursiv betyder at nogel refererer(henviser) til sig selv.
- rekursiv algoritme betyder at algoritmen refererer til sig selv og dermed gentager sig selv indtil opgaven er løst.
- Hvis mængden af data, der skal behandles, bliver mindre for hver rekursion (gentagelse), vil den rekursive algoritme selv standse, når den er løbet tør for data.
- Hvis mængden af data, der skal behandles, er den samme eller større, vil den rekursive algoritme forsætte uendeligt. Dermed er det vigtigt at indsætte en grænse for mængden af data der skal behandles, ellers vil en computer aldrig blive færdig med at udføre den rekursive algoritme.
Eksempel -Sierpinskis trekant:
 |
Denne trekant gentager sig 3 gange inde i sig selv, dermed stiger mængden af data med en faktor 3 for hver rekursion (gentagelse). Dermed går antallet af trekanter mod uendelig.
 |
En computer skal anvende uendelig lang tid til at tegne et uendeligt antal trekanter. Dermed er det vigtigt at begrænse, hvor mange gange computeren skal gentage den rekursive algoritme.
Rekursive algoritmer kan bruges til at tegne figurer, som kaldes for fraktaler. En fraktal er en figur, som gentager fragmenterede dele af sig selv inde i sig selv. Se eksempler på fraktaler og forskellige måder, som de kan tegnes på.
Opgave
- Hvor mange gange gentager Serpinskis kvadrat sig inde i sig selv pr. rekursion?
- Stiger mængden af data?
- Skal algoritmen for Serpinskis kvadrat begrænses eller standser den selv?
Fra 2D til 3D
Rekursive algoritmer behøver ikke kun at være i 2d, men kan også generes på samme måde i 3d:
L-system
L-systemer og blev udviklet af biologen Lindenmayer for at simulere alge vækst, men blev senere også anvendt til simulering af plantevækst. L-systemer er rekursive algoritmer, der laver eksakte kopier af sig selv.
 |
Eksempel på trævækst ved hjælp af L-system||
Foto af en broccoli, der ligner en L-system fraktal
 |
Innovativ opgave
Der findes mange løsninger til simulering af det samme mønster, f.eks. kan Sierpinskis trekant også generes ved anvendelse af et andet L-system:
Kan du finde på en rekursiv algoritme til at L-system fraktal? Brug et ternet stykke papir og tegn dit eget L-system.
Hvis du ikke kan finde på nogen, så kan du prøve at tegne Sierpinskis trekant eller Sierpinskis kvadrat:
En stokastisk generator (tilfældigheds generator)
Selvom at naturen laver kopier, så laver naturen aldrig eksakte kopier. Der er altid minimale forskelle, som vi har navngivet:
Tvillinger, søskende, familier, racer, arter osv. L-systemer laver altid eksakte kopier og det kan være nødvendigt at tilføje tilfældige forandringer (mutation) til hver eneste kopi, for at genskabe naturlige mønstere.
F.eks. kan Sierpinskis trekant bruges til at generere et 3d landskab, ved at man tilføjer tilfældige højde forandringer, for hver rekursion der udføres. Størrelsen på højdeforskellen bliver mindre for hver rekursion, så landskabet ikke bliver fuldstændigt tilfældigt (Se billedet til højere).
 |
Ved at sammensætte flere rekursive stokastiske algoritmer som f.eks. disse:
| Sierpinskis trekant med tilfældige højdeforskelle | + | L-system trævækst med tilfældige gren tykkelser, længder og vinkler | + | Træernes afkom med tilfældige afstande |
|---|---|---|---|---|
|
 |
 |
| Kan vi genere landskaber som disse: |
|---|
 |
Opgave
Gå sammen i grupper på 3-4 elever og diskuter, hvilke itterative og rekursive algoritmer der evt. skal sættes sammen, for at generere træbark, gulvbrædder, en græsplane, skyer og/eller andet I selv kan finde på.
Ekstra
Du kan gå ind på http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html, læse om Fibonacci tal og se hvilke mønstre der ligner rekursive mønstre.
