Godtyckligt nästlade datastrukturer

Skriv lösningarna till uppgifterna i en och samma fil och testa koden själv innan du använder rättningsskriptet. Att kunna testa sin kod är en viktig del av att programmera!

Att lära dig från uppgifterna

• Använda rekursion för att traversera godtyckligt nästlade strukturer.
• Lösa problem i nästlade strukturer med hjälp av dubbelrekursion.
• Kombinera rekursion och iteration för att hantera godtyckligt nästlade strukturer.

Man kan få max 100 poäng och för att få godkänt krävs 50 poäng (90 för väl godkänt). Försök dock att lösa alla uppgifter då inte alla fel upptäcks av rättningsskriptet. Om ni har lite marginal kan ni kanske bli godkända även om assistenten som rättar hittar något sådant fel.

Vi har tidigare använt rekursion för att lösa problem som att beräkna fakulteten av ett tal, summera en sekvens eller vända på en sträng. I samtliga fall har vi vid varje anrop av funktionen bara behövt göra ett ytterligare anrop av samma funktion. Vi har använt villkorssatser för att avgöra vilket anrop som skall göras, eller hur resultatet av anropet ska hanteras, men vi har alltid bara utfört som mest ett anrop. Denna typ av rekursion kallas för enkelrekursion och kan ses som ett alternativ till iteration.

Vi ska nu börja titta på situationer där vi vid varje anrop av funktionen behöver göra flera anrop av samma funktion. Denna typ av rekursion kallas för dubbelrekursion eller multipel rekursion. Detta kan inte på ett lika självklart sätt ersättas med iteration och det är här som rekursion verkligen kommer till sin rätt.

Vi kommer att börja med ett par klassiska matematiska exempel, för att sedan gå in på hur vi kan använda dubbelrekursion för att hantera godtyckligt nästlade strukturer.

Uppgift 12.1 (5p)

Skriv en funktion fib(n) som returnerar fibonaccitalet för position n.

Beräkning av fibonaccital är ett klassiskt exempel på dubbelrekursion. Fibonaccitalen definieras som följer:

$$ F(n)= \begin{cases} 0 & \mbox{om }n=0; \\ 1 & \mbox{om }n=1; \\ F(n-1)+F(n-2) & \mbox{om }n>1. \end{cases} $$

Med andra ord är fibonaccitalet för position n summan av fibonaccitalen för position n-1 och n-2. Detta innebär att för att beräkna F(n) måste vi först beräkna både F(n-1) och F(n-2), vilket i sin tur kräver ytterligare anrop av funktionen.

Du kan läsa mer om fibonaccital på Wikipedia.

OBS! Eftersom denna funktion är rekursiv och gör flera anrop till sig själv kan den bli mycket långsam för större värden av n. För att undvika detta, testa endast din funktion med små värden av n (t.ex. n < 20). Det är värt att veta att det finns mer effektiva sätt att beräkna fibonaccital, men här ska vi fokusera på den dubbelrekursiva implementationen enligt specifikationen ovan.

Exempel

>>> for i in range(20): print(fib(i), end=' ')
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Uppgift 12.2 (15p)

Skriv en funktion pascal(row, col) som returnerar talet på rad row och column col i pascals triangel. Du får inte använda den uttryckliga formeln för binomialkoefficienter för att lösa uppgiften.

Du kan läsa om pascals triangel på Wikipedia.

Tips 1: Börja med att sätta upp villkor för vilka värden på row och col som funktionen ska returnera 1, dvs för vilka värden på row och col är värdet högst upp, eller på en ytterkant.

Tips 2: Värdet är högst upp i triangeln när rad 1 efterfrågas. Värdet är på vänsterkanten när kolumnen är 1 och på högerkanten när rad och kolumn är samma tal.

Tips 3: Värdena som inte är på en ytterkant är summan av värdena ovanför. Du kan använda rekursiva anrop med modifierade rad och kolumnvärden för få dessa två värden.

Tips 4: För alla värden i Pascals triangel som inte är högst upp, eller på en ytterkant gäller $pascal(row, col) = pascal(row-1, col-1) + pascal(row-1, col)$

Exempel

>>> pascal(1, 1)
1
>>> pascal(2, 2)
1
>>> pascal(3, 2)
2
>>> pascal(5, 2)
4
>>> pascal(5, 3)
6
>>> pascal(5, 4)
4
>>> pascal(6, 3)
10

Vi ska nu titta på hur vi kan hantera godtyckligt nästlade strukturer med hjälp av rekursion. En godtyckligt nästlad struktur är en struktur som kan innehålla andra strukturer av samma typ (eller av andra kända typer), vilket innebär att vi inte vet i förväg hur djupt nästlingen kan gå.

Uppgifterna ska lösas med rekursion men ni får själva bestämma om ni vill använda explicit dubbelrekursion, en kombination av iteration och rekursion, eller någon form av ömsesidig rekursion. Ett förslag är att ni testar olika approacher på olika uppgifter och känner efter vad ni är mest bekväma med.

Uppgift 12.3 (10p)

Skriv en funktion keep_if_even_all(lst) som gör som keep_if_even i kapitel 4, men den undersöker också listor med godtycklig nästling. Om en lista bara innehåller udda tal ska den tomma listan sparas. Den ursprungliga listan får inte förändras.

Exempel

>>> keep_if_even_all([1, 2, [1, 3], [4, 7], 6])
[2, [], [4], 6]
>> keep_if_even_all([1, 2, [3, 4], [5, [6, 7, [[8]]]]])
[2, [4], [[6, [[8]]]]]

Uppgift 12.4 (10p)

Skriv en funktion is_in_list(lst, element) som returnerar True om element finns i lst, annars returnerar funktionen False. Funktionen ska undersöka även godtyckligt nästlade listor. Den ursprungliga listan får inte förändras.

Exempel

>>> is_in_list(["a", "b", "b", "a"], "b")
True
>>> is_in_list(["a", "b", "b", "a"], "c")
False
>>> is_in_list([1, 2, 3, [4, 5, [6]]], 6)
True
>>> is_in_list([1, 2, 3, [4, 5, [6]]], 7)
False

Uppgift 12.5 (10p)

Skriv en funktion count_all(lst) som returnerar antalet element som finns i lst. Funktionen ska undersöka också hantera godtyckligt nästlade listor. Ett annat sätt att tolka det är att ni ska räkna antalet löv i träd-tolkningen av lst

Exempel

>>> count_all(["a", "b", "b", "a"])
4
>>> count_all([1, 2, 3, [4, 5, [6]]])
6

Uppgift 12.6 (10p)

Skriv en funktion reverse_rec_all(lst) som gör som reverse_rec från kapitel 4 men den undersöker också godtyckligt nästlade listor. Den ursprungliga listan får inte förändras.

Exempel

>>> reverse_rec_all([1, [2, 3, 4], 5, 6])
[6, 5, [4, 3, 2], 1]
>>> reverse_rec_all([1, [2, 3], 4, [5, [6]]])
[[[6], 5], 4, [3, 2], 1]

Uppgift 12.7 (20p)

Skriv en funktion subst_all(lst, element, new_value) som returnerar en ny lista där alla förekomster av element har byts ut mot new_value. Funktionen ska också ersätta förekomster av element med new_value i godtyckligt nästlade listor. Den ursprungliga listan får inte förändras.

Exempel

>>> subst_all(["a", "b", "b", "a"], "b", "l")
['a', 'l', 'l', 'a']
>>> subst_all([1, 2, 3, [4, 5, [6]]], 6, "x")
[1, 2, 3, [4, 5, ['x']]]

Uppgift 12.8 (20p)

Skriv en funktion remove_duplicates(lst) som returnerar en version av lst där eventuella dubletter tagits bort. Bara den sista förekomsten av ett värde får vara kvar. Den ursprungliga listan får inte förändras.

Exempel

>>> remove_duplicates([1, 2, 3, 1, 4, 3])
[2, 1, 4, 3]
>>> remove_duplicates([[1], [2, 3], [[1, 4], [[3]]]])
[[], [2], [[1, 4], [[3]]]]