Förberedelsematerial 3.2

Vi har sett hur vi kan hantera nästlade datastrukturer med hjälp av loopar och uppslagning i dictionaries. I de exempel vi sett har vi dock alltid vetat i förväg hur många nivåer av nästling vi har att hantera, vilka nästlade element som är listor och vilka som är dictionaries, samt vilka nycklar eventuella dictionaries har.

I många fall vet vi dock inte i förväg hur strukturen ser ut, dvs. hur många nivåer av nästling som förekommer. I det här förberedelsematerialet ska vi titta på hur vi kan summera en godtyckligt nästlad lista (dvs. en lista där vi inte vet hur många nivåer av nästling som förekommer) av heltal med hjälp av rekursion.

En kort påminnelse om enkelrekursion

I avsnittet om enkelrekursion såg vi hur vi kunde summera en lista utan nästling med hjälp av rekursion.

Vi antar att vi har en lista [1, 2, 3] och vill beräkna summan av alla tal i listan. Vi kan använda följande enkelrekursiva funktion för att lösa problemet:

1
2
3
4
5

def sum_rec(values):
    if not values:
        return 0
    else:
        return values[0] + sum_rec(values[1:])

Notera att vi i Python ofta använder notationen if not values: för att kolla om en lista är tom, istället för if values == []:. Detta är det rekommenderade sättet enligt Pythons officiella stilguide PEP8. Vi kommer att använda den här konventionen i resten av förberedelsematerialet.

>>> print(sum_rec([1, 2, 3]))
6

Om du känner dig osäker på hur denna funktion fungerar, stega igenom den med hjälp av Python Tutor.

Men hur ska vi göra om vi har en lista som kan innehålla både tal och andra listor, till exempel [1, [2, 3], 4]? Om vi försöker använda samma funktion på denna lista kommer vi att få ett felmeddelande, eftersom vi i något steg kommer försöka slå ihop en lista ([2, 3]) med ett tal med +-operatorn. Det vet vi ju sedan tidigare att det kommer orsaka problem:

>>> print(sum_rec([1, [2, 3], 4]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in sum_rec
  File "<stdin>", line 5, in sum_rec
TypeError: can only concatenate list (not "int") to list

Kan vi använda iteration?

Innan vi går in på hur vi kan lösa detta med rekursion så kan vi fundera på om vi kan lösa det med iteration. Vi vet ju att alla enkelrekursiva funktioner kan skrivas om till iterativa funktioner, och vi har redan sett hur vi kan hantera nästling med iterativa funktioner. Vi kan ju iterera över alla element i listan och kolla om ett element är en lista eller ett tal. Om det är en lista kan vi iterera över den listan och addera dess element till summan. Om vi t.ex. har listan [1, [2, 3], 4] kan vi göra så här:

1
2
3
4
5
6
7
8
9

def sum_iter(values):
    acc = 0
    for element in values:
        if isinstance(values[0], list):
            for subelement in element:
                acc += subelement
        else:
            acc += element
    return acc

Notera att vi här använder isinstance(values[0], list) istället för type(values) == list eller type(values) is list för att kolla om det första elementet i listan är en lista. Detta är det rekommenderade sättet enligt Pythons officiella stilguide PEP8. Vi kommer att använda den här konventionen i resten av förberedelsematerialet.

Detta fungerar dock bara om vi vet att nästlingen är max 1 nivå djup. Om vi har en nästlad lista som [[1, 2], [3, [4, 5]]] kommer vi inte kunna hantera den med denna funktion, vi skulle behöva lägga till ytterligare en nivå av iteration för att hantera nästlingen i nästlingen.

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

def sum_iter_2levels(values):
    acc = 0
    for element in values:
        if isinstance(element, list):
            for subelement in element:
                if isinstance(subelement, list):
                    for subsubelement in subelement:
                        acc += subsubelement
                else:
                    acc += subelement
        else:
            acc += element
    return acc

På det här sättet kan vi fortsätta att lägga till fler nivåer av iteration för att hantera djupare nästling, men det är inte en särskilt flexibel lösning. Vi måste veta i förväg hur djup nästlingen kan vara och vi måste skriva om koden varje gång vi vill hantera djupare nästling. Det är inte heller särskilt elegant eller lättöverskådlig kod.

Istället ska vi titta på hur vi kan lösa detta med rekursion, vilket är en mycket mer flexibel lösning.

Dubbelrekursion

Vi kan modifiera vår rekursiva funktion sum_rec så att den kan hantera både tal och listor. Vi kallar denna nya rekursiva funktion för sum_nest_rec. Om det första elementet i listan är en lista, kan vi anropa sum_nest_rec på denna lista för att beräkna dess summa, och addera detta till summan av resten av listan. Om det första elementet är ett tal, kan vi addera detta tal till summan av resten av listan precis som tidigare. Vi börjar med en version med beskrivande kommentarer insprängda i koden:

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

def sum_nest_rec(values):
    # om vi inte har några värden är summan 0
    if not values:
        return 0
    # om första elementet är en lista, betrakta den listan som ett delträd och
    # summera dess värde rekursivt med resten av värdena i trädet
    elif isinstance(values[0], list):
        return sum_nest_rec(values[0]) + sum_nest_rec(values[1:])
     # om första elementet inte är en lista så betraktar vi det som ett löv
     # och adderar dess värde till resten av värdena i trädet
    else:
        return values[0] + sum_nest_rec(values[1:])

Här kommer samma kod igen, men utan kommentarerna, eftersom ibland kan vara svårt att läsa kod med mycket kommentarer när man är nybörjare. På sikt kommer man inse att kommentarer är värdefulla för att förstå koden och dess syfte, men det är naturligt att känna sig överväldigad innan man har en vana att läsa kod, och bara se en “wall of text”.

1
2
3
4
5
6
7

def sum_nest_rec(values):
    if not values:
        return 0
    elif isinstance(values[0], list):
        return sum_nest_rec(values[0]) + sum_nest_rec(values[1:])
    else:
        return values[0] + sum_nest_rec(values[1:])

Om vi testar denna funktion med vår nästlade lista får vi rätt resultat. Vi kan dock också testa med vår ursprungliga lista för att se att den fortfarande fungerar i det fallet också, samt med en mer komplex nästlad lista med flera nivåer av nästling.

>>> print(sum_nest_rec([1, [2, 3], 4]))
10
>>> print(sum_nest_rec([1, 2, 3]))
6
>>> print(sum_nest_rec([1, [2, 3], [[4, 5], 6]]))
21

Vi kan tydligt se på rad 8 i funktionen sum_nest_rec varför den här typen av funktion kallas just dubbelrekursiv. Vi anropar sum_nest_rec två gånger, en gång för att summera listan på första position i values och en gång för att summera resten av values. Det slutgiltiga resultatet är summan av dessa två delresultat.

Hur kommer det sig att den här typen av lösning fungerar? Vi ska titta på några olika sätt att förstå den här lösningen och känner du att en viss förklaring inte inte hjälper, så gå vidare. Resten av det här förberedelsematerialet kommer fokusera på olika sätt att tolka och skriva om sum_nest_rec och dess funktionalitet.

Tolkningar av lösningen

Som en summa över elementen på första nivån

Vi kan börja med att skriva om vår datastruktur lite för att skapa oss en tydligare bild av vad vi faktiskt arbetar med. Vi kan tänka oss att vi har en nästlad datastruktur som ser ut så här (det tredje exemplet ovan):

[1, [2, 3], [[4, 5], 6]]

Tittar vi noga ser vi att detta är en lista med 3 element: 1, [2, 3] och [[4, 5], 6]. Vi kan då formulera om detta som en serie additioner av värdet av varje element i listan:

get_value(1) + get_value([2, 3]) + get_value([[4, 5], 6])

Om vi kan beräkna get_value för varje del så kan vi addera dessa värden för att få den totala summan.

1 + 5 + 15

Vi har inte definierat get_value än utan använder det bara som ett sätt att tänka på problemet. Vi kan dock se att get_value måste kunna hantera både tal och listor. Om vi har ett tal som argument så är get_value bara talets värde. Om vi har en lista som argument så måste get_value summera värdet av varje element i listan. Det är ju precis det som vår rekursiva funktion sum_nest_rec gör. I avsnittet Uppdelning i två funktioner kommer vi titta närmare på hur den här tolkninen kan omsättas i kod.

Som ett uttryck med nästlade parenteser

Ett annat sätt att tänka på problemet är som en serie nästlade additioner:

1 + (2 + 3) + ((4 + 5) + 6)

Följer vi vanliga räkneregler och beräknar parenteserna inifrån och ut så får vi följande steg för att beräkna varje del av det ursprungliga uttrycket:

1 + (2 + 3) + ((4 + 5) + 6)
1 + 5 + ((4 + 5) + 6)
1 + 5 + (9 + 6)
1 + 5 + 15

Vi ser alltså att vi måste beräkna varje parentes innan vi kan addera ihop allt till en slutgiltig summa. Det är ju precis det som vår rekursiva funktion gör när den anropar sig själv på nästlade listor. Den beräknar summan av varje del och adderar slutligen ihop dessa summor.

Listan som en trädstruktur

Vi kan också tänka på den nästlade datastrukturen som ett träd där alla element i datastrukturen betraktas som löv eller som delträd som kan hanteras på samma sätt som alla träd.

Vi kan rita ut samma träd och de beräkningar som sker i varje steg av rekursionen på följande sätt:

[1, [2, 3], [[4, 5], 6]]
 |  |       |
 |  |       +---> [4, 5] + 6
 |  |             |        |
 |  |             |        +---> 6
 |  |             |
 |  |             +---> 4 + 5
 |  |
 |  +---> 2 + 3
 |
 +---> 1

Eller, genom att helt enkelt byta ut varje nod (cirklarna i diagrammet) som inte är ett löv mot den operation vi vill utföra på nodens barn. Ett sådant träd kallas för ett uttrycksträd (expression tree) och ser i vårt fall ut så här:

Vi kan alltså betrakta varje lista som ett delträd i en större trädstruktur. Vi kan sedan använda rekursion för att beräkna summan av varje delträd. När vi når ett löv (ett tal) adderar vi dess värde till summan av resten av trädet.

När vi tolkar datastrukturen som ett träd kallar vi det ofta för att vi traverserar trädet med hjälp av rekursion. Vi kan också säga att vi går ner i trädet när vi anropar funktionen rekursivt på ett delträd, och att vi går upp i trädet när vi returnerar värden “uppåt” i trädet.

Processen att översätta eller omtolka en datastruktur till en trädstruktur kallas ofta för parsning (parsing). Detta gäller speciellt när det är en sträng som översätts till en trädstruktur och detta kommer ni stöta på igen i t.ex. lingvistik- och språkteknologikurser i framtiden. Sådan parsning kan göras både av meningar i naturligt språk och av programkod. Parsning ingår alltså också som ett viktigt steg när pythontolken exekverar pythonkod.

(Om man vill kan man till och med inspektera trädstrukturen för ett stycke kod med hjälp av Pythons inbyggda ast-modul.)

Vad händer i anropsstacken?

Något som ofta är svårt att förstå med dubbelrekursion är hur anropsstacken ser ut. Det kan vara bra att rita upp anropsstacken för ett litet exempel för att se hur den växer och krymper när rekursionen går ner i trädet och sedan tillbaka upp igen. Man kan också stega igenom även denna lösning med hjälp av Python Tutor för att se hur anropsstacken ser ut i varje steg. Exemplet i länken använder listan [1, [2, 3], 4]. Du kan också testa med [1, [2, 3], [[4, 5], 6]] men det blir många steg att gå igenom.

Lite om terminologi

Vi sa att vi kallar lösningen ovan för dubbelrekursiv eftersom just 2 rekursiva anrop kan göras i varje evaluering av funktionen. Vi säger dock ofta att ett problem kräver en dubbelrekursiv lösning även om vi har fler än två rekursiva anrop i varje evaluering av funktionen. Det beror på att vi nästan alltid kan formulera om en funktion som gör fler än två rekursiva anrop till en funktion som gör max två rekursiva anrop, ett som utför det aktuella steget i beräkningen och ett som ser till att vi utför resterande steg i beräkningen.

Vi kan dock inte nödvändigtvis formulera om en funktion som gör två rekursiva anrop till en funktion som bara gör ett rekursivt anrop, och därför kan skrivas om till en loop, på ett enkelt sätt. Vi kommer se att vi kan flytta runt anropen, men vi kan inte eliminera den fundamentala egenskapen att vi för varje evalueringssteg kan behöva göra mer än ett rekursivt anrop. Den viktigaste skillnaden är alltså mellan en funktion som gör ett rekursivt anrop och en funktion som gör fler än ett rekursivt anrop och vi gör därför ofta en gränsdragning mellan enkelrekursion och dubbelrekursion.

I den bemärkelsen kan vi alltså beskriva problemet att summera en nästlad lista som “ett problem som kräver dubbelrekursion” eller “ett dubbelrekursivt problem”. Vi ska nu titta på ytterligare varianter av lösningen ovan för att visa på olika sätt att hantera dubbelrekursiva problem. Vi kan betrakta alla lösningar nedan som implicit dubbelrekursiva till skillnad från lösningen ovan som är explicit dubbelrekursiv.

Uppdelning i två funktioner

Det kan vara lättare att se hur den här typen av lösning fungerar om vi delar upp funktionen i två delar, en del som stegar framåt i listan på samma sätt som i den enkelrekursiva sum_rec, och en del som beräknar värdet för ett element i listan. Den del som beräknar värdet av ett element kan vi kalla get_value_rec och den del som hanterar att summera själva listan kan vi kalla sum_nest_rec_flat.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def sum_nest_rec_flat(values):
    if not values:
        return 0
    else:
        return get_value_rec(values[0]) + sum_nest_rec_flat(values[1:])

def get_value_rec(value):
    if isinstance(value, list):
        return sum_nest_rec_flat(value)
    else:
        return value

Detta kallas för ömsesidig rekursion (mutual recursion) eftersom de två funktionerna anropar varandra. Ibland kallar vi det också för indirekt rekursion, speciellt då vi har fler än två nivåer av funktioner som anropar varandra (fun_a anropar fun_b som anropar fun_c som anropar fun_a). Detta kan kontrasteras mot direkt rekursion, när en funktion anropar sig själv. Vi kan se att detta fungerar lika bra som den explicit dubbelrekursiva lösningen i en funktion ovan:

>>> print(sum_nest_rec_flat([1, [2, 3], 4]))
10
>>> print(sum_nest_rec_flat([1, 2, 3]))
6
>>> print(sum_nest_rec_flat([1, [2, 3], [[4, 5], 6]]))
21

Exemplet i Python Tutor

I praktiken har vi ju även här dubbelrekursion, eftersom vi för varje anrop till sum_nest_rec_flat gör ett anrop till get_value_rec, som i sin tur kan anropa sum_nest_rec_flat, och ett direkt anrop till sum_nest_rec_flat igen. Skillnaden är bara att vi har delat upp funktionaliteten i två delar och gett dem olika namn, vilket kan göra det lättare att förstå hur lösningen faktiskt fungerar.

Iteration och rekursion tillsammans i två funktioner

Vi har nu sett att vi kan dela upp en dubbelrekursiv funktion i två ömsesidigt rekursiva funktioner. Den ena av dessa, sum_nest_rec_flat, var en funktion som stegade framåt i listan på samma sätt som i vår enkelrekursiva sum_rec. Vi vet ju dock sedan tidigare att vi kan ersätta enkelrekursion med iteration.

Vi kan alltså skapa en iterativ version av sum_nest_rec_flat som vi kan kalla sum_nest_iter_flat. Vi skapar också en version av get_value_rec för ömsesidig rekursion med denna iterativa funktion och kallar den get_value_iter.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def sum_nest_iter_flat(values):
    acc = 0
    for element in values:
        acc += get_value_iter(element)
    return acc

def get_value_iter(element):
    if isinstance(element, list):
        return sum_nest_iter_flat(element)
    else:
        return element

>>> print(sum_nest_iter_flat([1, [2, 3], 4]))
10
>>> print(sum_nest_iter_flat([1, 2, 3]))
6
>>> print(sum_nest_iter_flat([1, [2, 3], [[4, 5], 6]]))
21

Exemplet i Python Tutor

Vi har fortfarande en implicit dubbelrekursiv lösning eftersom sum_nest_iter_flat anropar get_value_iter lika många gånger som det finns element i listan values och vart och ett av dessa anrop kan i sin tur leda till att sum_nest_iter_flat anropas. Eftersom anropen sker i en loop så görs alla anropen under en evaluering, alltså kan vi inte betrakta lösningen som enkelrekursiv.

Iteration och rekursion tillsammans i en funktion

Precis som de förra ömsesidigt rekursiva funktionerna så kan vi också skriva detta som en enskild funktion som använder både iteration och rekursion, utan att dela upp den i två delar. Vi kan kalla denna funktion sum_nest_iter.

Det är normalt sett denna typ av lösning som avses när vi talar om att hantera godtyckligt nästlade datastrukturer med hjälp av både rekursion och iteration. Iteration hanterar den yttre och “platta” strukturen, och rekursion hanterar nästlingen:

1
2
3
4
5
6
7
8

def sum_nest_iter(values):
    acc = 0
    for element in values:
        if isinstance(element, list):
            acc += sum_nest_iter(element)
        else:
            acc += element
    return acc

>>> print(sum_nest_iter([1, [2, 3], 4]))
10
>>> print(sum_nest_iter([1, 2, 3]))
6
>>> print(sum_nest_iter([1, [2, 3], [[4, 5], 6]]))
21

Exemplet i Python Tutor

Det ser ut som att vi i sum_nest_iter ovan har färre rekursiva anrop än i den dubbelrekursiva lösningen i sum_nest_rec, och det stämmer. Vi har i praktiken bytt ut den “yttre” rekursionen som hanterade den “platta” delen av strukturen mot en iteration. Dvs. det rekursiva anrop som stegade framåt i listan och som fanns med redan i den enkelrekursiva sum_rec, den dubbelrekursiva sum_nest_rec och i sum_nest_rec_flat är i sum_nest_iter_flat ersatt av en for-loop.

Vi ska dock inte lura oss att vi bara har ett rekursivt anrop kvar i sum_nest_iter. Vi måste komma ihåg att det rekursiva anropet sker inne i en loop, i värsta fall behöver vi göra ett rekursivt anrop för varje element i listan. Om vi t.ex. har listan [[1], [2], [3], [4], [5]] kommer vi att behöva göra 5 rekursiva anrop, ett för varje element i listan, medan iterationen utförs.

>>> print(sum_nest_iter([[1], [2], [3], [4], [5]]))
15  

Ett annat sätt att se det är att vi inte har minskat antalet rekursiva anrop som krävs för att hantera nästlingen. Vi har bara eliminerat de rekursiva anrop som krävdes för att stega framåt i listan. Vi kan också se det som det är nästlingen som gör att vi behöver rekursion, inte den yttre “platta” strukturen.

Sidospår: En högre ordningens funktion för get_value

I Python är funktioner “förstaklassmedborgare” (first-class members), vilket innebär att de kan behandlas som vilken annan datatyp som helst. Vi kan alltså skicka funktioner som argument till andra funktioner, och vi kan returnera funktioner från andra funktioner. En högre ordningens funktion (higher-order function) är en funktion som tar en funktion som argument och/eller returnerar en funktion som resultat.

Vi skulle t.ex. kunna använda högre ordningens funktioner för att skriva en version av vår funktion sum_nest_iter som är mer generell och som kan hantera andra typer av operationer än bara summering. Vi kan t.ex. skapa en funktion apply_nest_iter som tar en lista med nästlade element och en funktion func som argument, och som applicerar func på varje element i listan, oavsett om det är ett tal eller en lista. Vi kommer titta närmare på den här typen av högre ordningens funktioner längre fram i kursen.

Vad vi däremot kan göra redan nu är att titta på våra funktioner get_value_rec och get_value_iter. Dessa funktioner var ju näst intill identiska, med undantag för vad som hände om argumentet value var en lista. Den ena anropade den rekursiva sum_nest_rec_flat och den andra anropade den iterativa sum_nest_iter_flat. Vi kan skriva ut dessa två funktioner här igen:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def get_value_rec(value):
    if isinstance(value, list):
        return sum_rec_flat(value)
    else:
        return value

def get_value_iter(element):
    if isinstance(element, list):
        return sum_nest_iter_flat(element)
    else:
        return element

Dessa funktioner kan vi skriva om till en funktion get_value som tar en funktion som argument, och använder denna funktion för att hantera värden som är listor. Här har vi bara ändrat på listan med parametrar, för att ta emot en funktion func, och sedan använt denna funktion i stället för att hårdkoda anropet till sum_nest_rec_flat eller sum_nest_iter_flat.

1
2
3
4
5

def get_value(element, func):
    if isinstance(element, list):
        return func(element)
    else:
        return element

Vi kan sedan använda denna funktion i våra tidigare lösningar. Vi kan skriva om sum_nest_rec_flat och sum_nest_iter_flat så att de använder get_value istället för get_value_rec och get_value_iter.

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

def sum_nest_rec_flat(values):
    if not values:
        return 0
    else:
        return (
            get_value(values[0], sum_nest_rec_flat) +
                sum_nest_rec_flat(values[1:])
        )

def sum_nest_iter_flat(values):
    acc = 0
    for element in values:
        acc += get_value(element, sum_nest_iter_flat)
    return acc

På det här sättet behöver vi bara ändra på en plats om vi vill ändra på hur vi hanterar värden som är listor eller om vi vill ändra på hur vi hanterar löv (icke-listor).

Eller för den delen, om vi skulle vilja skapa en tredje version av sum_nest som använder en annan strategi för att hantera löv eller listor, eller om vi skulle vilja skapa en version som hanterar andra typer av nästlade datastrukturer än bara listor.

Beräkningskostnad

Det är viktigt att veta att dubbelrekursion ofta är väldigt ineffektivt. Om vi har en datastruktur som är mycket nästlad, och där varje element i datastrukturen är en lista med flera element, kan antalet rekursiva anrop växa mycket snabbt. Vi kommer under seminariet att titta på en dubbelrekursiv matematisk funktion som har den här egenskapen att den snabbt blir praktiskt taget oberäknelig.

Det är också viktigt att inse att rekursion alltid har en viss “overhead” (extra kostnad som alltid måste tas med i beräkningen) jämfört med iteration. Varje rekursivt anrop lägger ett nytt anrop på anropsstacken, och när funktionen returnerar tas detta anrop bort från stacken. Detta är en process som tar tid, och om vi har många rekursiva anrop kan denna overhead bli betydande. I praktiken är det därför ofta bättre att använda iteration där det är möjligt, och endast använda rekursion där det är nödvändigt för att hantera nästling.

Med andra ord vill vi helst undvika dubbelrekursion och ömsesidig rekursion. Alltså är den iterativa lösningen med rekursion i en funktion, sum_nest_iter, att föredra framför de andra lösningarna vi sett. Vi kan också se det i Python Tutor genom att anropsstacken för sum_nest_iter aldrig blir djupare än den maximala nivån av nästling, medan anropsstacken för speciellt lösningarna med ömsesidig rekursion kan bli mycket djup. Vi kan också se det i antalet steg som Python Tutor behöver för att visualisera lösningarna. Vår “bästa” lösning sum_nest_iter kan visualiseras för listan [1, [2, 3], 4] i 27 steg, medan den ömsesidiga rekursiva versionen krävde hela 51 steg. Denna lösning är alltså både den mest effektiva och den som kräver minst antal steg att visualisera.

Quiz

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