Pythonuppgifter 3.3 - Rekursion

Att lära dig från uppgifterna

• Hur man skriver rekursiva funktioner.

OBS! Alla uppgifter ska lösas rekursivt! Du får alltså inte använda for- eller while-loopar.

Godkänt

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

Uppgift 3.3.1 (10p)

Skriv en funktion fac_rec(n) som tar in ett tal och beräknar $n!=n\times (n-1)\times (n-2) \times … \times 1$.

Uppgift 3.3.2 (10p)

Skriv en funktion fib(n) som returnerar fibonaccitalet för position n. Om du är obekant med fibonaccital kan du läsa mer om det på wikipedia.

Uppgift 3.3.3 (10p)

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 mer 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 0 efterfrågas. Värdet är på vänsterkanten när kolumnen är 0 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)$

Uppgift 3.3.4 (10p)

Skriv en funktion keep_if_even(lst) vars argument lst är en lista med heltal. Funktionen returnerar en ny lista med de heltal i lst som är jämna.

Exempel:

1
2

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

Uppgift 3.3.5 (10p)

Skriv en funktion reverse_rec(lst) som tar en lista som inargument och returnerar en ny lista i omvänd ordning. Du ska inte undersöka listor-i-listor.

Exempel:

1
2

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

Exempel:

1
2

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

Uppgift 3.3.6 (15p)

Skriv en funktion keep_if_even_all(lst) som gör som keep_if_even i uppgift 3.3.4, men den undersöker också listor-i-listor. Om en lista bara innehåller udda tal ska den tomma listan sparas.

Exempel:

1
2

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

Exempel:

1
2

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

Uppgift 3.3.7 (15p)

Skriv en funktion reverse_rec_all(lst) som gör som reverse_rec men den undersöker också listor-i-listor.

Exempel:

1
2

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

Exempel:

1
2

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

Uppgift 3.3.8 (15p)

Skriv en funktion is_in_list(lst, element) som returnerar True om element finns i lst, annars returnerar funktionen False. Funktionen ska undersöka listor-i-listor.

Exempel:

1
2
3
4

>>> is_in_list(["a", "b", "b", "a"], "b")
True
>>> is_in_list(["a", "b", "b", "a"], "c")
False

Exempel:

1
2
3
4

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

Uppgift 3.3.9 (15p)

Skriv en funktion count_all(lst) som returnerar antalet element som finns i lst. Funktionen ska undersöka listor-i-listor.

Exempel:

1
2

>>> count_all(["a", "b", "b", "a"])
4

Exempel:

1
2

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

Uppgift 3.3.10 (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 undersöka listor-i-listor.

Exempel:

1
2

>>> subst_all(["a", "b", "b", "a"], "b", "l")
['a', 'l', 'l', 'a']

Exempel:

1
2

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

Uppgift 3.3.11 (15p)

Skriv funktionen multiply(factor1, factor2) som utför multiplikationen genom att addera factor1 till factor1, factor2 antal gånger med hjälp av rekursion.

Exempel:

1
2
3
4

>>> multiply(3, 7)
21
>>> multiply(7, 3)
21

Uppgift 3.3.E1

Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.

Skriv en funktion linear_serch(key, seq) som söker efter key (ett tecken eller ett listelement) i sekvensen seq (en sträng eller rak lista) och returnerar positionen. Om key ej finns i sekvensen så ska -1 returneras.

Exempel:

1
2
3
4
5

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

>>> linear_search('b', "anna")
-1

Tips 1

1
2
3
4
5
6
7

def linear_search(key, seq):
    """Sök efter nyckeln key i sekvensen seq.

    Returnerar ett tal som anger nyckelns position i sekvensen. Om key ej
    finns returnernas -1.
    """
    return linear_search_hlp(key, seq, 0)

Tips 2

Ett alternativ är att använda argument med default-värde (gås igenom på Föreläsning 4.1): linear_search(key, seq, index=0)

Uppgift 3.3.E2

Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.

Linjär sökning är ett ineffektivt sätt att söka. Ett betydligt snabbare sätt är att gör binär sökning. Binärsökning söker igenom en sorterad lista. Binärsökning börjar med att jämföra elementet i mitten av listan med det sökta värdet. Om det sökta värdet är lika med elementet i mitten av listan, returneras dess position i listan. Om det sökta värdet är mindre eller större än elementet i mitten av listan, så fortsätter sökningen i den lägre respektive högre halvan av listan, rekursivt

Skriv en funktion binary_search(key, sorted_lst) som söker efter key i den sorterade listan sorted_lst och returnerar positionen för key. Om key ej finns i sekvensen så ska -1 returneras.

Exempel:

1
2
3
4
5

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

>>> binary_search(0, [1,2,3,4,5,6,7,8,9])
-1

Tips: Använd två extra argument för low resp high för att representera index för start och slut på det listsegment du undersöker. Initialt är low = 0 och high = len(seq)-1

Uppgift 3.3.E3

Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.

Skriv rekursiva versioner av funktionerna insert_at_asc_place(values, new_value) och sort_asc(values) från uppgift 2.3.10-11. Namnge dem insert(lst, new_value) resp insertion_sort(lst)

Exempel:

1
2
3
4
5

>>> insertion([1, 11], 7)
[1, 7, 11]

>>> insertion_sort([3, 9, 7, 1, 11])
[1, 3, 7, 9, 11]

Uppgift 3.3.E4

Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.

Ett effektivare sätt att sortera listor på är med mergesort som är av typen “söndra och härska”. Om en lista har längden 1 är den sorterad och kan returneras, annars delas listan i två delar som sorteras och sedan sätts ihop.

Skriv de rekursiva funktionerna merge_sort(lst) och merge(sorted_lst1, sorted_lst2) där merge() tar två sorterade listor och sätter samman dem till en sorterad lista.

Exempel:

1
2
3
4
5

>>> merge([3, 9], [1, 7, 11])
[1, 3, 7, 9, 11]

>>> merge_sort([3, 9, 7, 1, 11])
[1, 3, 7, 9, 11]

Använda rättningsskriptet

OBS! Rättningsskriptet kan bara användas från LiUs Linux-miljö, dvs när du antingen är inloggad via ThinLinc, har anslutit via VSCodes RemoteSSH, inloggad på en dator i en Linux-sal via RDP, eller inloggad på en faktisk Linux-dator i en Linux-sal på Campus.

Du kan bara köra rättningsskriptet för en specifik uppgift (t.ex. Pythonuppgifter 1.2) en gång var åttonde minut. Detta är för att ni även behöver lära er hur ni testar er egen kod; ni ska inte vara beroende av att det finns ett rättningskript som hjälper er.

För att rätta din fil skriver du nedanstående ($ skrivs inte utan representerar prompten i terminalen):

1

$ /courses/TDDE44/kursmaterial/pyuppg/pytest.sh <uppgift> <kodfil>

• Ersätt <uppgift> med den uppgift koden löser, t.ex. 1_1 för att rätta Pythonuppgifter 1.1, 1_2 för Pythonuppgifter 1.2, 2_3 för Pythonuppgifter 2.3, osv.
• Ersätt <kodfil> med namnet på filen som innehåller din kod.
• OBS! Du måste stå i samma katalog som filen som du vill rätta.
• OBS! Du får inte döpa din kodfil till ett namn med en punkt i filnamnet (dvs utöver punkten innan ändelsen py. pyuppg1.1.py fungerar alltså inte.

Exempel

Exempel för Pythonuppgifter 1.1 om filen med dina lösningar är döpt till pythonuppg1_1.py

1

$ /courses/TDDE44/kursmaterial/pyuppg/pytest.sh 1_1 pythonuppg1_1.py

Exempel för Pythonuppgifter 2.3 om filen med dina lösningar är döpt till pyuppg23.py

1

$ /courses/TDDE44/kursmaterial/pyuppg/pytest.sh 2_3 pyuppg23.py

#### POÄNG (100 poäng behövs för GODKÄND UPPG) ####

UPPG 1.1: 5 poäng.
UPPG 1.2: 5 poäng.
UPPG 1.3: 5 poäng.
UPPG 1.4: 5 poäng.
UPPG 1.5: 10 poäng.
UPPG 1.7: 10 poäng.
UPPG 1.8: 10 poäng.
UPPG 1.9: 10 poäng.
UPPG 1.10b: 5 poäng.
UPPG 1.11: 15 poäng.
UPPG 1.12: 15 poäng.


#### SAKNADE UPPGIFTER ####

Kontrollera stavning på din funktioner. Stora och små
bokstäver spelar roll.

UPPG 1.10a saknar funktion: 'first_in_list'
UPPG 1.10c saknar funktion: 'last_in_list'


#### FEL vid TEST ####

Felsök genom att ha testanrop längst ner i din kodfil och
skriv ut resultaten. Kontrollera också så att du har mellanrum
på rätt ställe och att stora/små bokstäver stämmer överrens.

UPPG 1.6: Fel påträffades.

#### ANTAL POÄNG: 95
#### Du är INTE godkänd på Pythonuppgifter 1.
#### 5 poäng saknas.

------------------------ KOPIERA FRÅN RADEN UNDER DENNA ------------------------
dXBwZzEvaW5mby50eHRVVAkAAz99zVc/fc1XdXgLAAEE9QEAAAQUAAAABcHLEcIgEADQO1VsA3FY
zVd1eAsAAQT1AQAABBQAAABQSwMEFAAAAAgAiIElSZnJPKxkAAAAcgAAABgAHABqb2RmbzAxLXB5
AjhLN2E/iophTDike9+T7dQCwWNePC0+AeaCoWBy89Bfgdcutnt01j4K/FR+qxQY1xzjgbdxud6+
AGpvZGZvMDEtcHl1cHBnMS9taW5pZmllZC5weVVUCQADP33NVz99zVd1eAsAAQT1AQAABBQAAACN
UEsDBAoAAAAAAIiBJUkAAAAAAAAAAAAAAAAQABwAam9kZm8wMS1weXVwcGcxL1VUCQADP33NVz99
kstugzAQRfd8hUU3pCGhRMomUlb9jLayDIzBjbEte4iavy/YPEJaqV0gM3fO3Bk/RGu0RWKZqnQb
VcCJBeysolxcIdmcojEm8SDEnjBWKFwAHyYhv/EAqyrqsJdrt7Jo4DPexo6p4NM5oNgAvTLrsSuT
HZyPM+/j5+OKZbZO2Gi+NJ+VuXZSVsVSKCgssMtqKssqkr+rYTmEwVxXoGUlJn6CPPXL4a4m6Lug
hxIjBdJCSJmwVncKU9W1BViqOTWgjYS78kBkj4Q3KrUqGYLqv/kMXZ66+/Yu37rQlgvrkArVb82N
47rHOd3by0eYEXrz6k86D7Rk/3De5ZO1hBJpeEY/6aDvy0aLEqa0L6xBgR32avQFWq2oYi0kxgIX
X+BS13H/E656EM/rVhPZ33xgH/KzQUQG5/Nvxxs8xl7LExr46Im89g8GoSLFjZhbK5TgAixJGkTj
TllWC2y6Yl/qNpOCo+Y8W7BN9A1QSwMEFAAAAAgAiIElSclUPoaqAAAAqAEAAB8AHABqb2RmbzAx
zZoKdEnH7GDmmeo9xVhT5JpzNVmFaOPAK6G5P1BLAwQUAAAACACIgSVJoN99PmsBAABgAwAAGwAc
LXB5dXBwZzEvcHl1cHBnMXRlc3QubG9nVVQJAAM/fc1XP33NV3V4CwABBPUBAAAEFAAAAOPiUgYC
hQD/wy1+7goahgYGCgX5h5fkpSskpWYc3lZWrJB2eFuRgru/izdQhYtCaECAu6YCSA8XF4itYKhn
aKVgCtWkBxMzwiJmjEXMBIuYqZWCoQG6oBk2QXNsghbYBC2xCRoaJGKx3tAgCatoMjZRoN8NMUWN
CgAAAAAAiIElSQAAAAAAAAAAAAAAABAAGAAAAAAAAAAQAO1BAAAAAGpvZGZvMDEtcHl1cHBnMS9V
VAUAAz99zVd1eAsAAQT1AQAABBQAAABQSwECHgMUAAAACACIgSVJmck8rGQAAAByAAAAGAAYAAAA
AAAAUEsBAh4DFAAAAAgAiIElSaDffT5rAQAAYAMAABsAGAAAAAAAAQAAAKSBAAEAAGpvZGZvMDEt
AAABAAAApIFKAAAAam9kZm8wMS1weXVwcGcxL2luZm8udHh0VVQFAAM/fc1XdXgLAAEE9QEAAAQU
UEQhIezoF+LoAw1noLShKUTYpVTh8BKk8C04vFQhoLIkIz+vtKAgPTOtRMFQkUtBgQsAUEsBAh4D
JUnJVD6GqgAAAKgBAAAfABgAAAAAAAEAAACkgcACAABqb2RmbzAxLXB5dXBwZzEvcHl1cHBnMXRl
cHl1cHBnMS9taW5pZmllZC5weVVUBQADP33NV3V4CwABBPUBAAAEFAAAAFBLAQIeAxQAAAAIAIiB
c3QubG9nVVQFAAM/fc1XdXgLAAEE9QEAAAQUAAAAUEsFBgAAAAAEAAQAegEAAMMDAAAAAA==
------------------------- KOPIERA T.O.M. RADEN OVANFÖR -------------------------

Inlämning

När Pythonuppgifter 3.1-3.3 är färdiga är det dags att lämna in.

Inlämningar för Pythonuppgifter 1-3 behöver inte redovisas innan inlämning.

• Bifoga en textfil med rättningskoden för varje deluppgift. T.ex. för Pythonuppgifter 1 laddar ni upp 3 textfiler, en med rättningskoden för 1.1, en för 1.2 och en för 1.3.
• Hur du använder rättningsskripten står längst ner på varje sida med uppgifter.
• Inlämning av Pythonuppgifter:
  • Sendlab: Pythonuppgifter