Opstap¶

Deze pagina bevat uitvoerbare code.

Lezen en naspelen¶

Leerdoel: nagaan wat een recursieve functie doet, aanroep voor aanroep.

Deze opdrachten horen bij het eerste college. Voorspel bij elke opdracht eerst de uitvoer, en voer daarna de cel uit. Je kunt de code ook in Python Tutor plakken en er stap voor stap doorheen lopen; dan zie je de frames op de stack.

Opdracht 1¶

a. Wat doet de functie function?
b. Wat drukt dit programma af?

def function(x):
    print(x)
    if x == 0:
        return
    function(x - 1)


function(10)

Opdracht 2¶

a. Wat doet de functie function?
b. Wat drukt dit programma af?
c. Wat gebeurt er als je function(10, 2) vervangt door function(5, 0)? Voorspel het eerst, en probeer het dan.

def function(x, y):
    print(x)
    if x == 0:
        return
    function(x - y, y)


function(10, 2)

Opdracht 3¶

a. Wat doet de functie function?
b. Wat drukt dit programma af?

def function(x, y):
    print(x)
    if x >= 20:
        return
    function(x + y, y)


function(10, 6)

Opdracht 4¶

Hier combineert de functie het antwoord pas ná de recursieve aanroep, net als rest = fac(n - 1) in het college.

a. Wat geeft function("abc") terug?
b. Hoeveel frames van function staan er op het diepste punt tegelijk op de stack?
c. Wat doet de functie function?

def function(s):
    if s == "":
        return ""
    rest = function(s[1:])
    return rest + s[0]


print(function("abc"))

Schrijven¶

Leerdoel: een recursieve functie schrijven, met een basisgeval en een recursieve aanroep op een kleiner probleem.

Deze opdrachten horen bij het tweede college. Gebruik in opdracht 5 tot en met 11 recursie, en geen lus of comprehension. Opdracht 12 is de uitzondering: daar schrijf je dezelfde functie ook met een lus en met een list comprehension. Beantwoord eerst de drie vragen uit het college: wat is het basisgeval, wat is het kleinere probleem, en hoe combineer je?

Opdracht 5¶

Schrijf de functie add(m, n). Die geeft m + n terug, voor een n van 0 of groter. Tel daarbij alleen 1 op: schrijf m + n niet zelf.

Aanroep	Resultaat
`add(3, 4)`	`7`
`add(5, 0)`	`5`

Hint

Het basisgeval is n == 0. add(3, 4) is add(3, 3) + 1.

# jouw oplossing

assert add(5, 0) == 5
assert add(0, 0) == 0
assert add(3, 4) == 7
assert add(0, 3) == 3

Opdracht 6¶

Schrijf de functie product(L). Die geeft het product van de getallen in de lijst L: alle getallen met elkaar vermenigvuldigd.

Aanroep	Resultaat
`product([2, 3, 4])`	`24`
`product([])`	`1`

Hint

De rest van de lijst is L[1:], net als bij een string. Dit is de strategie van de dieven in opdracht 3 van het eerste college, maar nu vermenigvuldig je je eigen getal met het product van de rest. Het product van een lege lijst is 1: met 1 vermenigvuldigen verandert niets.

# jouw oplossing

assert product([2, 3, 4]) == 24
assert product([5]) == 5
assert product([7, 0, 3]) == 0
assert product([]) == 1

Opdracht 7¶

Schrijf de functie flip_bits(s). De string s bestaat uit nullen en enen; de functie geeft hem terug met elke 0 vervangen door een 1, en elke 1 door een 0.

Aanroep	Resultaat
`flip_bits("0110")`	`"1001"`
`flip_bits("")`	`""`

Hint

Draai het eerste teken om, en plak het vóór het antwoord op de rest.

# jouw oplossing

assert flip_bits("0110") == "1001"
assert flip_bits("1") == "0"
assert flip_bits("") == ""

Opdracht 8¶

Schrijf de functie no_punctuation(s). Die geeft de string s terug zonder de leestekens ., ,, ! en ?.

Aanroep	Resultaat
`no_punctuation("Hallo, wereld!")`	`"Hallo wereld"`
`no_punctuation("?!")`	`""`

Hint

Net als keepvwl uit het tweede college: hou het eerste teken, of laat het weg. Met s[0] in ".,!?" vraag je of het een leesteken is.

# jouw oplossing

assert no_punctuation("Hallo, wereld!") == "Hallo wereld"
assert no_punctuation("?!") == ""
assert no_punctuation("") == ""

Opdracht 9¶

Schrijf de functie only_odds(L). Die geeft een lijst met de oneven getallen uit L, in dezelfde volgorde.

Aanroep	Resultaat
`only_odds([3, 8, 5, 0, 7])`	`[3, 5, 7]`
`only_odds([2, 4])`	`[]`

Hint

Een getal x is oneven als x % 2 == 1. Je bouwt een lijst op. Hou je het eerste element, dan plak je [L[0]] voor het antwoord op de rest.

# jouw oplossing

assert only_odds([3, 8, 5, 0, 7]) == [3, 5, 7]
assert only_odds([2, 4]) == []
assert only_odds([]) == []

Opdracht 10¶

Een palindroom is een woord dat achterstevoren hetzelfde is, zoals lepel of kok. Schrijf de functie is_palindrome(s). Die geeft True als s een palindroom is, en anders False.

Aanroep	Resultaat
`is_palindrome("lepel")`	`True`
`is_palindrome("lepels")`	`False`
`is_palindrome("")`	`True`

Hint

Een string met hoogstens één teken is altijd een palindroom. Dat is dus het basisgeval: len(s) <= 1. Is het eerste teken s[0] anders dan het laatste, s[-1], dan ben je meteen klaar. Anders kijk je naar wat ertussen staat: s[1:-1].

# jouw oplossing

assert is_palindrome("lepel") == True
assert is_palindrome("kok") == True
assert is_palindrome("lepels") == False
assert is_palindrome("ab") == False
assert is_palindrome("a") == True
assert is_palindrome("") == True

Opdracht 11¶

Twee woorden rijmen in deze opdracht op n letters als hun laatste n letters gelijk zijn. Zo rijmen kater en water op 4 letters: allebei eindigen ze op ater. Dat kun je recursief bepalen, vanaf het eind:

Is n gelijk aan 0, dan geef je True terug.
Is een van de twee woorden leeg, dan geef je False terug.
Is de laatste letter van het ene woord niet gelijk aan de laatste letter van het andere, dan geef je False terug.
Anders roep je de functie opnieuw aan, met beide woorden zonder hun laatste letter en met n - 1, en geef je het resultaat daarvan terug.

Schrijf de functie rhymes(word1, word2, n) volgens deze regels.

Aanroep	Resultaat
`rhymes("kater", "water", 4)`	`True`
`rhymes("kat", "kip", 1)`	`False`
`rhymes("aap", "schaap", 4)`	`False`

Hint

Elke regel wordt één tak van je if, in dezelfde volgorde. De laatste letter van s is s[-1], en alles ervóór is s[:-1].

# jouw oplossing

assert rhymes("kater", "water", 4) == True
assert rhymes("kat", "rat", 2) == True
assert rhymes("kat", "kip", 1) == False
assert rhymes("aap", "schaap", 3) == True
assert rhymes("aap", "schaap", 4) == False

Opdracht 12¶

Deze opdracht is een voorbereiding op het oefententamen. Daar schrijf je dezelfde functie op drie manieren: met een lus, met een list comprehension en met recursie. Welke manier het mooiste is, doet hier niet ter zake; het tentamen vraagt ze alle drie.

Schrijf drie functies die de getallen uit L teruggeven die groter zijn dan 0, in dezelfde volgorde:

positives_loop(L), met een lus;
positives_lc(L), met een list comprehension;
positives_rec(L), met recursie.

Aanroep	Resultaat
`positives_loop([3, -1, 0, 7, -5])`	`[3, 7]`
`positives_lc([-2, 0])`	`[]`
`positives_rec([])`	`[]`

Hint

De recursieve versie heeft dezelfde vorm als only_odds uit opdracht 9.

# jouw oplossing

assert positives_loop([3, -1, 0, 7, -5]) == [3, 7]
assert positives_loop([-2, 0]) == []
assert positives_loop([]) == []

assert positives_lc([3, -1, 0, 7, -5]) == [3, 7]
assert positives_lc([-2, 0]) == []
assert positives_lc([]) == []

assert positives_rec([3, -1, 0, 7, -5]) == [3, 7]
assert positives_rec([-2, 0]) == []
assert positives_rec([]) == []