4. Mer om rekursion

4.1 Inledning

I denna laborationsomgång ska vi gräva oss djupare in i rekursion och upptäcka nya användningsområden. Vi kommer även att tydligare jämföra iteration och rekursion. Ibland kan det finnas situationer där rekursion är mer lämpligt eller till och med är nödvändigt att använda.

Studiematerial

Innan denna labb påbörjas bör följande studiematerial ha lästs:

• Dubbelrekursion
• Hur man programmerar
• Programmeringspraxis
• Listbyggare

4.2 Mer om upprepning

Iteration handlar om att utföra en följd av instruktioner flera gånger. När det handlar om att utföra samma sak med varje element i t.ex. en lista brukar vi säga att vi itererar över listan. Vi kan köra det genom att använda explicit index så här:

for i in range(len(my_list)): print(my_list[i])

Här räknar vi ut listans längd och låter variabeln i anta alla värden i intervallet 0 till listans längd minus ett. På det sättet behandlar vi alla element. Ett sätt som många gånger kan vara lättare är att göra så här:

for e in my_list: print(e)

Här använder vi inget index. Det tar for-loopen själv hand om. Den erbjuder oss elementen i listan, ett i taget, i variabeln e. Detta sätt funkar inte bara på listor och strängar, utan också på i princip alla sammansatta datatyper som kan indexeras. Till exempel funkar det för tupler och dictionaries som vi ju redan har övat på lite grann. När det gäller dictionaries itererar vi främst över indexmängden, d v s alla nycklarna.

I de följande övningarna tänker vi oss främst iterativa lösningar, d v s du behöver inte konstruera rekursiva varianter.

Övning 401

Konstruera en funktion show_wordlist som går genom en dictionary och skriver ut vad de olika nycklarna svarar mot.

>>> show_wordlist(numbers) -- one - 1 eight - 8 two - 2 --

Den exakta ordningen mellan elementen spelar ingen roll. Den kan variera. Hur anpassar du for-loopen så att du kan gå igenom en dictionary?

Övning 402

Konstruera en funktion all_pairs som utifrån en lista ger en lista med alla par, d.v.s. alla möjliga sätt att kombinera två element ur originallistan. Paren representeras som tupler och vi ser dem som ordnade. Det innebär att om x och y är två olika element, så är (x, y) och (y, x) två olika möjliga par.

>>> all_pairs([1, 2, 3]) [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]

Om vi skickar in en lista av längden n ska vi givetvis få en lista med n^2 antal par i som resultat.

Övning 403

Konstruera en funktion unordered_pairs som utifrån en lista ger en lista med alla oordnade par. Utdata ska vara precis som i föregående övning, tupler i en lista. Skillnaden är att här ser vi paren som oordnade. Det innebär t.ex. att om paret (1, 2) finns med i resultatet, så får inte (2, 1) vara det. Par som (1, 1) tillåts dock, så länge som det bara finns en kopia av dem.

>>> unordered_pairs([1, 2, 3]) [(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)]

Om vi skickar in en lista av längden n ska vi här få en lista med n(n+1)/2 < antal par i som resultat.

Övning 404

Konstruera en funktion distribute som tar ett element och en lista av listor, och lägger in elementet i varje dellista. Listan man skickar in ska inte ändras, utan funktionen ska generera en helt ny lista.

>>> old = [['tesc'], ['fo'], [1]] >>> distribute("o", old) [['tesc', 'o'], ['fo', 'o'], [1, 'o']] >>> old # har listan ändrats? [['tesc' ], ['fo'], [1]]

Övning 405

Konstruera en funktion extend_each som tar ett element och en lista av listor, och lägger in elementet i varje dellista. Skillnaden mot funktionen ovan är att denna funktion faktiskt ska ändra på listan som skickades in.

>>> extend_each("o", old) >>> old # har listan ändrats? [['tesc', 'o'], ['fo', 'o'], [1, 'o']]

Övning 406

Konstruera en funktion push_strings som tar en lista och knuffar alla strängar ett steg fram. Den första strängen hamnar alltså på den plats den andra strängen hade förut, och så vidare. På den första strängens plats ska det stå 0. Den sista strängen försvinner. Listan ska inte modifieras, utan en ny lista ska returneras.

>>> eggs = [1, 't', 3, 4, 'e', 5, 's'] >>> eggs = push_strings(eggs) >>> eggs [1, 0, 3, 4, 't', 5, 'e'] >>> push_strings(eggs) [1, 0, 3, 4, 0, 5, 't']

Lös problemet på två olika sätt, först i en version som itererar över listans element (for element in list), sedan i en version som itererar över indexmängden (for i in range(len(list))). Hur skiljer sig lösningarna åt?

Övning 407

Konstruera en funktion merge_lists som tar en lista med två listor. Elementen i dessa två underlistor ska läggas i en ny lista. Den nya listan ska returneras i stigande ordning. Vi kan anta att elementen i de två underlistorna är i stigande ordning.

>>> seq = [[0, 1, 2, 3, 4], [0, 0, 1, 4, 10]] >>> merge_lists(seq) [0, 0, 0, 1, 1, 2, 3, 4, 4, 10]

Denna övning är mer lämplig att lösas rekursivt. Varför? Hur skulle man lösa det här iterativt?

4.3 Dubbelrekursion

I laboration 3 stötte du på enkelrekursion, d.v.s. rekursion där vi bara bearbetade den översta nivån i listan. Nu använder vi liknande mönster för att hantera strukturer eller beräkningar som i någon mening förgrenar sig ("listor i listor"). Du kan läsa mer om detta i kapitlet Dubbelrekursion i studiematerialet.

Övning 408 Skriv en funktion sum_all_numbers som lägger samman alla tal i en lista, oavsett vilken nivå de ligger på. Listan kan i sin tur innehålla listor, och alla tal ska läggas samman.

>>> sum_all_numbers(["a", "b", ["c", 3, 4, [5, "d"], 10], 9]) 31

Övning 409 Skriv en funktion exists som avgör om en viss bokstav finns på någon nivå i en lista. Det är ett predikat, så returvärdet ska vara True eller False.

>>> exists("c", ["a", ["h", "e", "j"], ["t", "e", "s", "c", "o"]]) True

Övning 410 Skriv en funktion without_vowels som utifrån en lista ger dig en ny likadan struktur, men utan alla vokaler. OBS! Här kan vi ha listor-i-listor (till skillnad från i laboration 1).

>>> test = ["a", ["h", "e", "j"], ["t", "e", "s", "c", "o"]] >>> without_vowels(test) [['h', 'j'], ['t', 's', 'c']]

4.4 Binärträd - rekursivt definierade strukturer

En klassisk datastruktur är det binära trädet, ett träd där varje förgrening maximalt utmynnar i två grenar (subträd). En speciell sorts binärträd är binära sökträd som kan användas för att lagra stora mängder information som man snabbt behöver hitta. I ett korrekt binärt sökträd är alla värden i vänstra grenen mindre än värdena i högra grenen. Exempel:

5 / \ 3 7 / / \ 1 6 8

Informationen som lagras i trädet kallas nycklar, i ovanstående exempel enbart heltal. Varje punkt i trädet med en nyckel kallas en nod, och noden "längst upp" i trädet kallas rotnoden. I detta träd har roten värdet 5. Trädet har också tre noder som är löv (1, 6 och 8), d.v.s. punkter i trädet som inte förgrenar sig vidare. De noder som inte är löv kallar vi för inre noder. Det finns också några subträd, d.v.s. träd som börjar en bit in i strukturen. Du kommer att läsa mer om träd inom den diskreta matematiken, men detta räcker för stunden. Här är samma exempel nedbrutet i sina beståndsdelar:

Hela trädet Subträd (i) Subträd (ii) Löv (iii) Löv (iv) Löv (v) 5 / \ 3 7 3 7 / / \ / / \ 1 6 8 1 6 8 1 6 8

Vi ser att rotnoden har två barn, 3 och 7. De är i sin tur rotnoder för var sitt subträd (i) och (ii). Det vänstra subträdet har ett barn (1), det högra har två (6, 8). Dessa barn är i sin tur träd - löv med enstaka värden. Om vi betraktar det som att 3 har ett tomt träd som högerträd, ser vi att ett träd definitionsmässigt kan vara tre olika saker:

1. Inget alls (det tomma trädet)
2. En enda nyckel (trädet är enbart ett löv)
3. En nyckel samt två subträd (vänster och höger), där åtminstone något av subträden har ett innehåll

Den här datastrukturen är rekursivt definierad eftersom vi i den tredje punkten hänvisar tillbaka till hela definitionen för vad ett träd är. Binära sökträd borde därför lämpa sig utmärkt att bearbeta rekursivt, gärna med utgångspunkt i ovanstående definition.

Representation

Än så länge har vi bara beskrivit hur binära sökträd ser ut och ritat upp dem lite informellt. Om vi vill kunna få in dem i Python och bearbeta dem måste vi komma på ett sätt att representera dem med hjälp av de inbyggda datastrukturerna i Python.

I de här övningarna väljer vi representationen [<vänster subträd>, <nyckel>, <höger subträd>] för en inre nod, [] för det tomma trädet medan nycklarna är vanliga heltal. Subträdet (i) med sin tomma högergren, från exemplet ovan, ser alltså ut så här:

[1, 3, []]

Subträd (ii) ser ut så här:

[6, 7, 8]

Hela trädet blir då:

[[1, 3, []], 5, [6, 7, 8]]

Jämför hur vi ritade upp detta binära sökträd i exemplet ovan med listrepresentationen för Python. Det är antaligen mycket lättare för dig att visualisera trädet om du ritar upp det så som vi gjorde först i det här avsnittet. Tittar man bara på listrepresentationen är det dock rätt krånligt att se hur trädet hänger ihop. När du gör övningarna och uppgiften nedan kan det vara bra att rita upp dina exempelträd, så som vi har gjort ovan, innan du översätter dem till listformat.

Övningar

För att kunna jobba med binära sökträd finns i filen tree.py (i ditt Git-arkiv) ett antal hjälpfunktioner:

• is_empty_tree kontrollerar om trädet är tomt
• is_leaf kontrollerar om trädet är ett löv
• create_tree tar två subträd och ett nyckelvärde och skapar ett träd av dessa
• left_subtree returnerar det vänstra subträdet
• right_subtree returnerar det högra subträdet

Alla dessa funktioner är mycket korta och innehåller bara enkla manipuleringar av listor. Tanken med att använda dem är att koden blir betydligt mer lättläst. Istället för att skriva my_tree[0] kan vi skriva left_subtree(my_tree) och hjälper på så sätt den som ska läsa koden. Dessutom kommer vi att kunna ändra representation på träden i efterhand, eller använda program skrivna av folk som använder en annan representation (men samma selectors) direkt, utan att behöva fundera på om trädet i Python skrivs som listor, tupler eller något annat.

Övning 411 Skriv en funktion key, som tar ett träd (inre nod eller löv) och ger tillbaka nyckeln.

>>> key([[1, 3, []], 5, 6]) 5

Övning 412 Skriv en funktion is_treelike, som tar något indata, och kontrollerar att det verkar vara ett träd. (Kontroll av subträd behöver inte ske, utan det räcker att det ser trädliknande ut på toppnivån.)

>>> is_treelike([[1, 3, []], 5, 6]) True >>> is_treelike([1, 2, ['fel','data']]) True >>> is_treelike([]) True >>> is_treelike(42) True >>> is_treelike([4711]) False

Övning 413 Skriv en funktion is_proper_tree, som tar någon slags struktur, och undersöker om det är ett träd. Här måste man såklart kontrollera att inte bara översta nivån verkar vara ett träd (lista, 3 element, ...). Skapa gärna hjälpfunktioner med väl valda namn, och använd de givna funktionerna så långt det går.

>>> is_proper_tree([]) True >>> is_proper_tree([[1, 3, []], 5, 6]) True >>> is_proper_tree([[[]], 5, 6]) False

Övning 414 I ett binärt sökträd är alla nycklar i vänster subträd mindre än eller lika med nyckeln i rotnoden, och alla till höger är större. Skriv en funktion exists_in_tree, som undersöker om ett visst värde på ett löv finns i trädet. Du behöver inte alltid gå igenom alla värden i trädet (så som vi gjorde i uppgift 301).

>>> exists_in_tree(6, [[1, 3,[]], 5, [6, 7, 8] ]) # exempelträdet ovan True >>> exists_in_tree(666, [[1, 3,[]], 5, [6, 7, 8] ]) False >>> exists_in_tree(7, [[1, 3,[]], 5, [6, 7, 8] ]) True

Övning 415 Skriv en funktion insert som - i ett färdigt binärt sökträd - lägger till ett värde på rätt plats. Det kan hända att värden som tidigare var löv blir inre noder, och du kan anta att värdet inte redan finns i trädet. (Det är annars lätt att lägga till en kontroll innan funktionen körs.)

>>> our_tree = insert(5, []) # börja med ett tomt träd 5 >>> our_tree = insert(10, our_tree) # 10 är större än 5, så det hamnar i höger subträd [[], 5, 10] >>> our_tree = insert(7, our_tree) # 7 är större än 5, mindre än 10 [[], 5, [7, 10, []]] >>> our_tree = insert(1, our_tree) [1, 5, [7, 10, []]]

Övning 416 Skriv en funktion print_tree som skriver ut löven storleksordning.

>>> print_tree(our_tree) # trädbygge från exempelkoden ovan 1 7