Upprepning

En klassisk roadtrip-låt

99 bottles of beer on the wall, 99 bottles of beer.
Take one down, pass it around. 98 bottles of beer.
98 bottles of beer on the wall, 98 bottles of beer.
Take one down, pass it around. 97 bottles of beer.
97 bottles of beer on the wall, 97 bottles of beer.
Take one down, pass it around. 96 bottles of beer.
96 bottles of beer on the wall, 96 bottles of beer.
Take one down, pass it around. 95 bottles of beer.
95 bottles of beer on the wall, 95 bottles of beer.
Take one down, pass it around. 94 bottles of beer.
94 bottles of beer on the wall, 94 bottles of beer.
Take one down, pass it around. 93 bottles of beer.
93 bottles of beer on the wall, 93 bottles of beer.
Take one down, pass it around. 92 bottles of beer.
...
...

Låten fortsätter så tills man kommer ner till "0 bottles of beer". Om vi vill skriva ett program som ska skriva ut texten till denna låt kan vi skriva 198 print-satser i följd, men ett smartare sätt vore att använda oss av särskilda programstrukturer för upprepning istället för att klippa och klistra. Ni kommer senare att få se att det då räcker med 4 rader kod. Dessutom blir koden mycket mer flexibel, eftersom vi kommer att kunna ange ett godtyckligt antal flaskor att börja med.

Vi vill skriva en funktion som räknar ner ett tal i från 99 till 1. För varje i ska den skriva ut de två sångraderna med i på rätt ställe.

Vi vill ha något i denna stilen:

for i in range(???):
    print(???)

Hur fungerar range()?

För att se hur range() fungerar visar vi här lite körexempel.

>>> for i in range(4):
...     print(i)
...
0
1
2
3
>>> list(range(4))
[0, 1, 2, 3]
>>> list(range(1,4))
[1, 2, 3]
>>> list(range(4,0,-1))
[4, 3, 2, 1]

Det finns tre olika sätt att använda range():

• range(slut) som ger en sekvens från 0 till, men inte med, slut.
• range(start, slut) som ger en sekvens från start till, men inte med, slut.
• range(start, slut, steg) som ger en en sekvens från start till, men inte med, slut, med steglängd steg.

start, slut och steg måste vara heltal. En tom sekvens ges om inget giltigt interall är givet.

Överkurs: Man kan tänka sig att range() returnerar en lista av tal -- men för att vara mer effektiv skapar den inte en lista på en gång. Istället kan den helt enkelt beräkna ett nytt tal i taget, just när man behöver nästa tal. Det är därför vi använder list(range(...)) i exemplen ovan: Anropet till list(...) ber om ett nytt tal i taget ända till det tar slut, och skapar en lista av alla de talen.

Dokumentation

Bottles of beer on the wall

Vi kan nu skriva en funktion som skriver ut vår låttext med hjälp av upprepning.

Iterativ version

def song(n):
    for i in range(n,0,-1):
        print(f"{i} bottles of beer on the wall, {i} bottles of beer")
        print(f"Take one down, pass it around, {i-1} bottles of beer on the wall")

På rad 2 säger vi att i ska börja på n och gå ner till (men inte inklusive) 0. -1 som steglängd ser till att vi räknar neråt istället för uppåt. På rad 3 och 4 skriver vi ut en del av låttexten med i insatt på rätt ställe. Dessa rader kommer att upprepas varje steg tills det att i har nått 0.

Som vi ser går det nu utmärkt att ange ett godtyckligt antal flaskor att börja med. Vi kan till exempel anropa song(1000) och börja med 1000 flaskor, utan att behöva klippa och klistra ett antal extra rader. Detta är värt att göra även om man från början bara hade 2-3 repetitioner! Det minskar också risken att man gör fel när man klipper och klistrar, och det visar intentionen bakom koden: Det syns direkt att vi ska göra nästan samma sak i varje steg (inga subtila skillnader i steg 42 som är lätta att missa), och det syns direkt vad som skiljer sig mellan de olika stegen (i). Det blir alltså lättare att se att koden faktiskt gör vad vi ville.

Det här är en iterativ funktion. Vi ska nu kolla hur vi kan skriva funktionen på ett rekursivt sätt.

Rekursiv version

En rekursiv funktion är en funktion som anropar sig själv. Detta använder man ofta när man kan lösa ett problem om man vet svaret till mindre instanser av samma problem (som vi snart kommer att se i fakultetsfunktionen).

För att börja nosa lite på begreppet gör vi först bara en mycket enkel variant av rekursion, där vi "itererar med hjälp av funktionsanrop". Här beräknar vi egentligen aldrig lösningen på något delproblem -- istället gör vi utskrifter.

Så här kan då en rekursiv variant av sången se ut:

def song(i):
    if i > 0:
        print(f"{i} bottles of beer on the wall, {i} bottles of beer")
        print(f"Take one down, pass it around, {i-1} bottles of beer on the wall")
        song(i - 1)

På rad 3-4 gör vi samma sak som i den iterativa varianten, vi skriver ut låttexten och skriver in i på rätt ställe. Efter att vi har skrivit ut texten för ett visst i så anropar vi funktionen igen med _i-1 (har vi nyss skrivit ut texten för i=8 så vill vi skriva ut den för i=7 efter).

För att se till att funktionen någon gång slutar anropa sig själv har vi på rad 1 en if-sats som ser till att koden bara körs om song anropas med ett i som är större än 0. Försäkra er själva om att funktionen körs för evigt om if-satsen inte är där.

Iteration och rekursion när man beräknar ett värde

Men varför vill man loopa med hjälp av rekursion?

Ofta vill man inte det. Tänk dig istället att vi inte vill skriva ut något utan istället vill beräkna ett värde: Vi vill skapa en lista som innehåller alla textrader i sången.

I en iterativ version kan det se ut så här:

def song(n):
    result = []
    for i in range(n,0,-1):
        result.append(f"{i} bottles of beer on the wall, {i} bottles of beer")
        result.append(f"Take one down, pass it around, {i-1} bottles of beer on the wall")

I en rekursiv version kan vi istället göra så här:

def song(i):
    if i == 0:
        return []
    else:
        return [f"{i} bottles of beer on the wall, {i} bottles of beer",
                f"Take one down, pass it around, {i-1} bottles of beer on the wall"] + song(i - 1)

Här har vi ett basfall där vi har 0 flaskor kvar. Då är sånglistan tom: Vi returnerar [].

Vi har sedan ett fall där vi har minst 1 flaska kvar. Hur ska vi lösa detta? Jo, vi vet vilka textrader som ska vara först om man börjar med exakt i flaskor -- de två strängarna som vi lägger i en första lista i koden ovan. Sedan kan vi ju göra ett anrop till song(i-1) för att få reda på hur man fortsätter när man har druckit upp en flaska och bara har i-1 flaskor kvar!

Fakultet

Vi provar en gång till, nu med fakultetsversionen.

Iterativ version

Fakulteten av n är produkten av alla tal från 1 till n, där n>=1.

n! = n x (n - 1) x (n - 2) x ... x 2 x 1

Hur kan man skriva detta i Python-kod?

def factorial(n):
    res = 1
    for i in range(2, n + 1):
        res = res * i
    return res

Vi börjar med att sätta resultatet till 1. På rad 3 säger vi sedan att vi vill gå igenom alla tal från 1 till (men inte inklusive) n+1. Inuti for-loopen multiplicerar vi varje sådant tal på resultatet (rad 4). Till slut skickar vi tillbaka resultatet med en return-sats.

Vi testar programmet:

>>> factorial(5)
120

Rekursiv

Vi upprepar definitionen av rekursion (men hoppar över specialfallet n=0 just nu):

n! = n x (n - 1) x (n - 2) x ... x 2 x 1

Detta gäller för alla n. Om vi antar att k är minst 2, och sätter in n=k och n=k-1, kan vi se att:

k! = k x (k - 1) x (k - 2) x ... x 2 x 1

(k-1)! = (k - 1) x (k - 2) x ... x 2 x 1

Som du ser är (k-1)! lika med den högra delen av definitionen av k!. Med andra ord har vi att:

k! = k * (k - 1)!

givet att k>=2. Och om k=1 vet vi redan att k!=1.

Alltså kan vi skriva att k! är:

• 1 om k är 1,
• k * (k-1)! annars.

Här är det återigen så att man kan lösa ett problem om man vet svaret till mindre instanser av samma problem -- om vi vet (k-1)! kan vi snabbt räkna ut k! genom en extra multiplikation.

Hur kan man skriva det i Python-kod?

def factorial(k):
    if k == 1:
        return 1
    else:
        return k * factorial(k - 1)

Den första raden i raden i den matematiska definitionen är basfallet som ser till att rekursionen slutar. Här ser vi att rad 2-3 i Python-koden är basfallet. Vi kollar här ifall k är lika med 1, är detta sant så returnerar vi 1. Alla rekursiva funktioner måste ha ett basfall för att se till rekursionen slutar.

Rekursionsfallet (den nedre raden i den matematiska definitionen) motsvaras av rad 4-5 i Python-koden. Här returneras värdet av k multiplicerat med fakulteten av k-1. För att räkna ut fakulteten av k-1 så använder vi factorial-funktionen igen. Rekursionsfallet måste se till att problemet går mot basfallet.

Missa inte att rekursionen löste ett delproblem av samma typ -- för att räkna ut ett fakultetsproblem fick man också räkna ut ett annat fakultetsproblem. Det är detta som identifierar en rekursiv lösningsmodell.

Tillhörande quiz

Finnes här