Rekursion och fraktaler (överkurs)

Här får du lära dig

• vad rekursion är
• hur rekursion kan användas för att rita fraktaler

Med rekursion i programmering menas funktioner som anropar sig själv. Med den tekniken kan vi rita spännande geometriska mönster, så kallade fraktaler.

En viktig detalj när funktioner anropar sig själva är att det finns ett stoppvillkor. Annars skulle funktionen anropa sig själv i all oändlighet.

En annorlunda stjärna

Tidigare i kursen av vi ritat en femuddig stjärna. Nu när vi lärt oss både repetitioner och funktioner kan vi förenkla koden.

def stjärna(sida):
    for i in range(5):
        forward(sida)
        right(144)

stjärna(250)
      

Nu ska vi göra om funktionen stjärna till en rekursiv funktion som anropar sig själv. I varje udd ska en ny mindre stjärna ritas och i de mindre stjärnorna ska i sin tur en liten stjärna finnas i varje udd. Och så vidare i ett djup vi anger.

För att kunna skriva ett stoppvillkor kommer vi använda if n == 0: return vilket betyder "om n är lika med 0, gå ur funktionen". I varje rekursivt steg kommer n minska med ett. Därför kommer funktionen att sluta anropa sig själv när n är lika med 0. Du kan läsa mer om if-satsen här.

Studera exemplet nedan noggrant. Försök att förstå exakt vad som händer. Rekursion är inte lätt att förstå i början!

def stjärna(sida, n):
    if n == 0:
        return
    for i in range(5):
        forward(sida)
        stjärna(sida/3, n-1)
        right(144)

stjärna(150, 3)
      

I exemplet ovan är raden stjärna(sida/3, n-1) den viktiga delen. Den innebär att det ritas en ny stjärna med en tredjedel så stor sida och med ett djup som är ett lägre. Med stjärna(150, 3) är sidan från början 150 och djupet 3. Efter att en sida ritats kommer stjärna(50, 2) anropas, det vill säga rita en stjärna med sidan 50 och djup 2. I nästa steg är djupet 1 och då ritas en enkel stjärna. Vid djupet 0 ritas inte längre något på grund av stoppvillkoret.

Kochs snöflinga

Kochs snöflinga är en av de första beskrivna fraktalerna och skapades av den svenska matematikern Helge von Koch år 1904. Nu ska vi se hur vi kan rita den med hjälp av rekursion. Algoritmen nedan beskriver hur snöflingan ritas.

1. Börja med en rak linje.
2. Dela linjen i tre lika stora delar.
3. Ersätt den mittersta delen med två delar som bildar en spets uppåt.
4. Upprepa för alla linjer.

# Klicka på testa för att se illustrationen.

  

För att rita fraktalen så kan vi börja med att rita det grundläggande mönstret i en funktion. Därefter kan vi ersätta varje linje med ett rekursivt anrop.

def snöflinga(sida):
    forward(sida)
    left(60) #vinkeln är 60 grader i en liksidig triangel
    forward(sida)
    right(120)
    forward(sida)
    left(60)
    forward(sida)
  

Nu ska vi byta ut forward(sida) mot snöflinga(sida/3,n-1). Istället för att rita ut en linje gör vi ett nytt mönster där linjen skulle ha varit. Det nya mönstret är endast en tredjedel så stort. Stoppvillkoret när n = 1 är helt enkelt att rita ut sträckan. Det är basfallet som du kan se i algoritmens steg 1.

def snöflinga(sida,n):
    if n == 1: #stoppvillkoret
        forward(sida)
        return

    snöflinga(sida/3,n-1) #istället för forward(100)
    left(60)
    snöflinga(sida/3,n-1) #istället för forward(100)
    right(120)
    snöflinga(sida/3,n-1) #istället för forward(100)
    left(60) 
    snöflinga(sida/3,n-1) #istället för forward(100)