Förberedelsematerial 2.1

Innan du börjar med kapitel 4 av Pythonuppgifterna och inför Storseminarium 2.1 ska du gå igenom materialet nedan, vilket bör ta ca en timme. Du bör också genomföra det tillhörande quizet längst ner på sidan, som testar dina kunskaper på materialet. Quizet finns endast till för att du ska kunna skatta dina egna kunskaper, och är inget du bedöms på.

Problembeskrivning

Tidigare uppgifter vi har arbetat med har varit relativt enkla, i den meningen att vi har jobbat med operationer som bearbetar data en enstaka gång. Detta begränsar dock våra möjligheter att lösa större problem där samma operationer behöver upprepas mer än en gång. För att kunna hantera sådana problem kommer vi nu att introducera en metod som kallas för rekursion, eller mer specifikt, enkelrekursion.

Det finns fler sätt att åstadkomma upprepning inom programmering, men alla utom rekursion kräver att vi introducerar ny syntax. För att använda rekursion räcker det med de konstruktioner vi redan arbetat med, vi behöver bara tillämpa dem på ett smart sätt.

Du som programmerat lite tidigare kanske undrar varför vi inte använder loopar för att åstadkomma upprepning. Vi kommer att titta på loopar också, men lite längre fram i kursen kommer vi att stöta på problem som inte kan lösas på ett enkelt sätt med bara loopar så fokusera på att lära dig behärska rekursion först.

Idén bakom rekursion är att lösa ett större problem genom att stegvis bryta ner ett problem till mindre eller enklare instanser av samma problem. Efter denna förenkling kan vi anropa funktionen igen, inifrån sig själv, för att lösa det enklare problemet. Vi kallar den typ av rekursion vi kommer behandla nedan för enkelrekursion eftersom vi kommer att göra som mest en sådan förenkling och rekursivt anrop (när funktionen anropar sig själv) varje gång funktionen exekveras. (Om några veckor kommer vi att titta på dubbel- eller multipelrekursion, där vi kan behöva göra flera rekursiva anrop vid en och samma exekvering, men det väntar vi med.)

Ett första exempel

För att börja nosa lite på begreppet tar vi ett enkelt exempel. Här beräknar vi egentligen aldrig lösningen på något delproblem utan gör bara utskrifter och förenkling.

Med hjälp av formatsträngar kan vi skriva en rekursiv funktion som skriver ut texten till den klassiska sången 99 Bottles of beer:

1
2
3
4
5
6
7

def print_song(i):
    if i < 1:
        return
    else:
        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")
        print_song(i - 1)

Vi får en utskrift ungefär i den här stilen:

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.
...

På rad 5-6 skriver vi ut sångtexten och sätter in i (som är ett heltal) på rätt ställe. Efter att vi har skrivit ut texten för ett visst i så anropar vi funktionen igen på rad 7 med i-1 som argument. Har vi nyss skrivit ut texten där i är 8 så vill vi nu skriva ut den för fallet där i är 7.

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

*Med “för evigt” menas här “tills pythontolken säger ifrån”.

Bygga upp ett resultat

Oftast vill vi med en rekursiv funktion bygga upp något resultat. I print_song skrev vi bara ut varje rad direkt på skärmen, men säg att vi istället ville ha en lista med alla rader i sången. Det kan vi åstadkomma genom att skriva:

1
2
3
4
5
6
7
8

def list_song(i):
    if i < 1:
        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"
        ] + list_song(i-1)

Nu skrivs inget ut, så för att se resultatet måste vi skicka resultatet av funktionsanropet till print, d.v.s. print(list_song(99)).

Komponenter i en rekursiv funktion

Låt oss titta närmare på hur programstrukturen hos ett enkelrekursivt program kan se ut. Vi kommer använda nedanstående anatomiska sketch där vi ersatt de olika operationerna med anrop till funktioner med namn som beskriver komponentens syfte. I praktiken kan dessa funktionsanrop motsvaras av vilken typ av uttryck som helst. Oftast kommer vi inte behöva definiera sådana funktioner utan kan skriva enklare uttryck direkt som vi gjorde i song och song2.

1
2
3
4
5
6
7

def rec_fun(argument):
    # Basfall
    if has_trivial_solution(argument):
        return trivial_solution
    # Ett eller flera (med elif) rekursionsfall
    else:
        return combine(do_something(argument), rec_fun(simplify(argument)))

Basfall

Det är oftast enklast att börja titta på basfallet hos en rekursiv funktion. Tanken här är att vi vill identifiera minst ett fall där beräkningen av returvärdet är trivial. Oftast behöver vi inte ens göra en beräkning utan kan returnera ett färdigt svar, som i list_song, eller bara avsluta funktionen, som i print_song. I båda fallen visste vi att sången var slut när det inte längre fanns några flaskor kvar (if i < 1:) och vi avslutade utan att göra något ytterligare rekursivt anrop. Ibland kan man behöva flera sådana fall men för enkelrekursion har vi oftast bara ett.

I list_song returnerade vi en tom lista när i < 1. Detta beror på att en lista konkatenerad med den tomma listan är lika med den ursprungliga listan. D.v.s. [1, 2, 3] + [] → [1, 2, 3] och, faktiskt, [] + [] → []. Alltså, om vi stegvis bygger upp en lista är att konkatenera med [] samma sak som att inte lägga till något alls, och det är ju precis vad vi vill när vi är färdiga.

Vi kallar villkoret som identifierar basfallet för ett stoppvillkor och i den anatomiska sketchen rec_fun är stoppvillkoret resultatet av funktionsanropet has_trivial_solution(argument). Vanliga stoppvillkor är t.ex. när ett argument är exakt 0, mindre än något värde, exakt 1, en tom sekvens, eller när vi hittat eller uppnått ett visst värde. Mer komplexa stoppvillkor förekommer, men det är inget vi kommer stöta på här.

I print_song och list_song motsvarades has_trivial_solution(argument) alltså av i < 1 i if-satsen.

Några av er kanske råkade skapa en rekursiv funktion av misstag i samband med Pythonuppgifter kapitel 1-3 där ni fick felmeddelandet RecursionError: maximum recursion depth exceeded. Detta är just vad som händer om det saknas ett korrekt stoppvillkor och rekursionen fortsätter för länge.

Rekursionsfall

Om vi ännu inte uppnått stoppvillkoret så behöver vi beskriva ett (eller flera, då får vi använda elif) fall som består av följande komponenter:

1. do_something(argument): Gör något med det aktuella värdet på argument. I rec_fun beskrev vi det som do_something(argument) men oftast behöver det som sagt inte vara ett funktionsanrop. I print_song motsvarades do_something(argument) av utskrifterna av versens två rader medan i list_song motsvarades det av att skapa en lista med de raderna som element.
2. simplify(argument): Förenklar argumentet. Att “förenkla” betyder i det här sammanhanget att vi förändrar argumentet på ett sådant sätt att vi tar ett steg närmare stoppvillkoret. I print_song och list_song motsvarades detta av uttrycket i-1 i anropet print_song(i-1) respektive list_song(i-1) på den sista raden.
3. rec_fun(simplify(argument)): Gör ett rekursivt anrop till funktionen med det förenklade värdet som argument. I print_song och list_song motsvarades detta av anropet print_song(i-1) respektive list_song(i-1) på den sista raden
4. return combine(do_something(argument), rec_fun(simplify(argument))): Eventuellt så kombinerar vi resultatet av do_something(argument) med resultatet av det rekursiva anropet. I print_song behövde vi varken returnera eller kombinera något eftersom vi bara skrev ut något på skärmen. I list_song byggde vi dock stegvis upp en lista och vi konkatenerade varje steg med +. D.v.s. return combine(do_something(argument), rec_fun(simplify(argument))) i den anatomiska sketchen motsvarades i list_song av:

1
2
3
4

        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"
        ] + list_song(i-1)

Olika sätt att använda rekursion

Som exempel i det här avsnittet tänker vi oss uppgiften att räkna ut det totala värdet av alla mynt i en plånbok.

Vi representerar mynten i plånboken som en lista av heltal: [1, 10, 5, 5, 2, 1, 1]

Rekursiv processlösning

Ett första sätt att lösa problemet är att utföra följande manöver

• Om det inte finns några mynt i plånboken så är värdet av alla mynt i plånboken $0$.
• Om det finns mynt, ta upp ett mynt. Värdet av av alla mynt i plånboken är värdet av myntet vi plockade upp plus värdet av de mynt som nu finns kvar i plånboken.

Det är lätt att tro att vi inte har en färdig lösning här. Vi har ju nämligen inte sagt något om hur vi beräknar “värdet av alla mynt som finns kvar i plånboken”. Det kan vi dock göra genom applicera precis samma lösning igen.

• Om det inte finns några mynt i plånboken så är värdet av alla mynt i plånboken $0$.
• Om det finns mynt, ta upp ett mynt. Värdet av av alla mynt i plånboken är värdet av myntet vi plockade upp plus värdet av de mynt som nu finns kvar i plånboken.

Om vi bara fortsätter att göra detta kommer vi till slut att nå fallet då det inte längre finns några mynt kvar och värdet av alla mynt i plånboken är $0$.

I det föregående steget, då vi måste ha plockat upp det sista myntet, blir alltså värdet av alla mynt i plånboken lika med värdet av myntet vi plockade upp plus $0$. Detta kan vi använda för att beräkna värdet av det föregående steget då vi måste plockat upp det näst sista myntet. I det steget blir värdet av alla mynt i plånboken värdet av det näst sista myntet adderat till värdet av det sista myntet.

Så kan vi fortsätta tillbaka genom alla steg vi tagit tills vi återvänder till den ursprungliga frågan och på vägen tillbaka har vi, steg för steg, räknat ut det totala värdet.

Motsvarande lösning i kod skulle kunna se ut som följande:

1
2
3
4
5
6
7

def count_money_rp(wallet):
    if wallet == []:
        return 0
    else:
        return wallet[0] + count_money_rp(wallet[1:])

count_money_rp([1, 10, 5, 5, 2, 1, 1])

Även om count_money_rp står sist på sista raden, så är det rekursiva anropet inte det sista som sker. För att additionen wallet[0] + count_money_rp(wallet[1:]) ska kunna utföras måste vi ju ta reda på vad wallet[0] och count_money_rp(wallet[1:]) är. Alltså sker additionen först efter att det rekursiva anropet returnerat.

Det kan vara svårt att visualisera detta, så vi gör en variant där vi kan skriva ut varje enskilt steg. Vi börjar med att introducera variablerna first_coin, rest_of_wallet, value_of_rest, och total_value i funktionen:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def count_money_rp(wallet):
    if wallet == []:
        total_value = 0
        return total_value
    else:
        first_coin = wallet[0]
        rest_of_wallet = wallet[1:]
        value_of_rest = count_money_rp(rest_of_wallet)
        total_value = first_coin + value_of_rest
        return total_value

Den här lösningen är ekvivalent med lösningen ovan. Dvs. vi utför exakt samma operationer i exakt samma ordning för att lösa problemet, vi har bara introducerat några beskrivande namn på olika komponenter i vår lösning.

Eftersom vi i båda klausulerna i if-satsen avslutar med att returnera total_value så kan vi också flytta retursatsen till den sista raden och utanför if-satsen:

1
2
3
4
5
6
7
8
9

def count_money_rp(wallet):
    if wallet == []:
        total_value = 0
    else:
        first_coin = wallet[0]
        rest_of_wallet = wallet[1:]
        value_of_rest = count_money_rp(rest_of_wallet)
        total_value = first_coin + value_of_rest
    return total_value

När vi gjort detta kan vi lägga till utskrifter som motsvarar vad vi beskrev i processen ovan. Vi använder f-strängarna som vi introducerade i song för att skriva ut stegen i vår lösning:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def count_money_rp(wallet):
    print(f"Mynt i plånboken: {wallet}")
    if wallet == []:
        print("Inga mynt finns kvar.")
        total_value = 0
    else:
        first_coin = wallet[0]
        rest_of_wallet = wallet[1:]
        print(f"Vi plockar upp ett mynt med värdet {first_coin} och beräknar värdet av resten ({rest_of_wallet}) av mynten i plånboken.")
        value_of_rest = count_money_rp(rest_of_wallet)
        print(f"Värdet av resten av mynten i plånboken är {value_of_rest} och vi adderar det till värdet av myntet vi plockade upp: {first_coin} + {value_of_rest}.")
        total_value = first_coin + value_of_rest
    print(f"Värdet av alla mynt i plånboken är {total_value}.")
    return total_value

count_money_rp([1, 10, 5, 5, 2, 1, 1])

Notera att vi egentligen inte utför några additioner förrän vi har nått stoppvillkoret och returnerat $0$. För att en addition ska kunna utföras så måste pythontolken först ta reda på värdena som skall adderas.

Först när vi kommer till basfallet vet vi vad “värdet av alla mynt som finns kvar i plånboken” faktiskt är och kan börja slå ihop värdena av mynten. Om du kör koden ovan kommer utskrifterna också visa att vi utför additionerna “bakifrån”. Det kan komma som en överraskning, men kom ihåg att vi var tvugna att räkna ut “värdet av alla mynt som finns kvar i plånboken”, innan vi kunde räkna ut värdet av alla mynten. I praktiken innebär det just att vi utför additionerna “bakifrån”.

Ett annat sätt att beskriva det är att vi skjuter uträkningen framför oss tills vi har ett trivialt värde av alla mynt i plånboken ($0$, när plånboken är tom) som vi kan utgå ifrån för att räkna ihop den totala summan. Det här sättet att utföra rekursion kallas för en rekursiv processlösning och är i någon mening det “enklaste” sättet att lösa ett problem med rekursion.

“Enkelt” ska dock inte tolkas som att det är konceptuellt självklart vad som händer. Tvärt om är det få saker inom programmering som kan verka lika mycket som svart magi första gången man ser det, som den här typen av rekursion. Snarare ska “enkelt” tolkas som att, som vi såg i första exemplet, vi kan skriva lösningen utan att behöva introducera några extra variabler. De extra variabler vi introducerade använde vi ju enbart för att sätta namn på saker vi redan gjorde och för att kunna skriva ut stegen vi utförde.

Detta kan verka något bakvänt första gången man stöter på det, och vi ska därför titta på ett alternativt sätt att lösa problemet rekursivt.

Iterativ processlösning

I den rekursiva processlösningen ovan så skjöt vi den faktiska beräkningen framför oss. Det var först när vi kommit till slutet och de rekursiva anropen började returnera några värden som vi de faktiska additionerna kunde utföras. Ett alternativt sätt att lösa problemet är med en så kallad iterativ processlösning.

Lösningen i det här fallet kan beskrivas som följande:

• Om det finns mynt, ta upp ett mynt och addera dess värde till värdet av alla mynt du redan plockat upp, upprepa för resten av plånboken. (Rekurssionssteget)
• Om det inte finns några mynt i plånboken så är värdet av alla mynt som fanns i plånboken lika med värdet av alla mynt du har plockat upp. (Basfallet)

Här har vi lagt till ett koncept, värdet av alla mynt du plockat upp, som inte fanns med i den rekursiva processlösningen. Vi behöver representera detta som en extra variabel som, till skillnad från våra extra utskriftsvariabler ovan, är nödvändig för den lösning vi beskriver. Vi kallar den här typen av värde för en ackumulatorvariabel eller bara ackumulator eftersom vi använder den för att ackumulera ett resultat.

I kod skriver vi som vanligt basfallet först:

1
2
3
4
5
6
7

def count_money_ip(wallet, accumulated_value):
    if wallet == []:
        return accumulated_value
    else:
        return count_money_ip(wallet[1:], accumulated_value+wallet[0])

count_money_ip([1, 10, 5, 5, 2, 1, 1], 0)

Den här lösningen är inte ekvivalent med count_money_rp som vi såg ovan. Resultatet vi får i slutändan är detsamma, men beräkningarna vi utför för att komma fram till resultatet sker i en annan ordning än i alla varianter av count_money_rp. Istället för att skjuta på additionerna tills plånboken är tom så håller vi hela tiden koll på värdet av alla mynt vi hittills plockat upp. Det betyder också att vi måste skicka med 0 när vi anropar funktionen eftersom vi måste veta värdet av de mynt vi har plockat upp. Det värdet är ju $0$ om vi inte har plockat upp några mynt alls än.

Precis som i den rekursiva processlösningen kan vi dela upp komponenterna och ge dem mer beskrivande namn för att tydligare kunna skriva ut vad som sker:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def count_money_ip(wallet, accumulated_value):
    if wallet == []:
        total_value = accumulated_value
        return total_value
    else:
        first_coin = wallet[0]
        new_accumulated_value = accumulated_value + first_coin
        rest_of_wallet = wallet[1:]
        total_value = count_money_ip(rest_of_wallet, new_accumulated_value)
        return total_value

Här har vi en lösning som är ekvivalent med count_money_ip. Precis som i fallet med den rekursiva processlösningen så ser vi att vi returnerar samma sak i slutet av varje klausul och kan därför flytta retursatsen till den sista raden och utanför if-satsen.

1
2
3
4
5
6
7
8
9

def count_money_ip(wallet, accumulated_value):
    if wallet == []:
        total_value = accumulated_value
    else:
        first_coin = wallet[0]
        new_accumulated_value = accumulated_value + first_coin
        rest_of_wallet = wallet[1:]
        total_value = count_money_ip(rest_of_wallet, new_accumulated_value)
    return total_value

Vi kan nu lägga till utskrifter för att demonstrera vad som sker i varje steg:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def count_money_ip(wallet, accumulated_value):
    if wallet == []:
        print("Inga mynt finns kvar.")
        total_value = accumulated_value
    else:
        first_coin = wallet[0]
        new_accumulated_value = accumulated_value + first_coin
        print(f"Vi plockar upp ett mynt med värdet {first_coin} och adderar det till värdet av mynten vi redan plockat upp ({accumulated_value} + {first_coin} = {new_accumulated_value}).")
        rest_of_wallet = wallet[1:]
        print(f"Upprepa för resten av plånboken ({rest_of_wallet}).")
        total_value = count_money_ip(rest_of_wallet, new_accumulated_value)
    print(f"Värdet av alla mynt i plånboken är {total_value}.")
    return total_value

Som vi ser om vi kör den här koden så sker additionen innan vi gör det rekursiva anropet. Det innebär också att när vi nått slutet så är beräkningarna färdiga och vi kommer att returnera samma värde från alla de rekursiva anropen.

Sätt slippa skicka med en ackumulator vid första anropet

Vid anropet till count_money_ip var vi tvugna att skicka med ett initialt värde för accumulated_value:

1

count_money_ip([1, 10, 5, 5, 2, 1, 1], 0)

Detta är en av anledningarna till att den iterativa processlösningen ibland betraktas som lite mindre “elegant” än den rekursiva processlösningen. Vissa problem, speciellt de där varje steg bygger på resultatet av det föregående steget, är dock ofta mer naturliga att lösa på det här sättet.

Eftersom det inte är särskilt elegant att behöva skicka med samma värde varje gång vi vill anropa en rekursiv funktion som använder en iterativ processlösning så ska vi titta på tre sätt att komma runt detta.

En viktig detalj är att inga av metoderna nedan förändrar lösningen, vi förändrar bara hur det initiala anropet till funktionen sker. Att vi illustrerar tre olika sätt ska ses som ett exempel på att vi inom programmering ofta kan lösa ett visst problem på mer än ett sätt.

Wrapperfunktioner

Det enklaste sättet är att definiera count_money som en så kallad wrapper-funktion. Det är en funktion som “slår in” anropet till en annan funktion och förenklar anropet till den:

1
2

def count_money_wrap(wallet):
    return count_money_ip(wallet, 0)

Här behöver den som använder count_money_wrap inte veta något om hur count_money_ip måste anropas och huruvida det behövs ett initialt värde på en eller flera ackumulatorvariabler eller liknande. Denna approach fungerar i princip i alla programmeringsspråk, och används inte bara när vi arbetar med rekursion. Nackdelen med detta är att count_money_ip fortfarande måste vara definierad och tillgänglig för vem som helst att använda. Det kan göra det förvirrande om vissa delar av en större kodbas använder count_money_wrap medan andra använder count_money_ip och orsaka följdproblem pga den förvirringen.

Nästlade funktioner

Många språk, t.ex. Python, tillåter att vi definierar funktioner inuti andra funktioner. Detta kallas för nästlade funktioner. Vi kan använda detta för att komma runt problemet med att wrapper-funktionen innebär att vi har två olika funktioner som gör samma sak men anropas på lite olika sätt:

1
2
3
4
5
6
7
8

def count_money_nest(wallet)
    def inner(wallet, accumulated_value):
        if wallet == []:
            return accumulated_value
        else:
            return inner(wallet[1:], accumulated_value + wallet[0])

    return inner(wallet, 0)

Den inre funktionen inner är bara tillgänglig inne i count_money_nest och det finns alltså ingen risk att den anropas någon annanstans i koden. Nästlade funktioner kan vi också använda om vi vill skapa hjälpfunktioner som bara ska användas av en enda funktion.

Det är dock viktigt att veta att detta inte är tillåtet i flera populära språk som t.ex. C, C++ och Java. Språk som JavaScript bygger å andra sidan i stor utsträckning just på att arbeta med nästlade funktioner.

Defaultparametrar

Även om nästlade funktioner är praktiska och har många användningsområden så behöver vi faktiskt inte använda dem för just det här fallet. Istället kan vi ge parametern accumulated_value ett så kallat defaultvärde (denna svengelska term används i Skansholms bok så det får vara okej). En parameter med ett defaultvärde, eller en defaultparameter, är en parameter som automatiskt får ett visst värde om inget argument skickas med.

Här vill vi ju att accumulated_value ska få värdet 0 om inget annat anges och vi kan skriva det som nedan:

1
2
3
4
5

def count_money_default(wallet, accumulated_value=0):
    if wallet == []:
        return accumulated_value
    else:
        return count_money_default(wallet[1:], accumulated_value+wallet[0])

Quiz

Testa din förståelse av materialet med tillhörande quiz