Opstap¶
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 one_to_sum(n). Die geeft de som van de getallen 1 tot en met n. Gebruik geen sum.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
Hint
Het basisgeval is n == 0. one_to_sum(5) is 5 + one_to_sum(4).
# jouw oplossing
assert one_to_sum(0) == 0
assert one_to_sum(1) == 1
assert one_to_sum(3) == 6
assert one_to_sum(5) == 15
Opdracht 6¶
Schrijf de functie sum_list(L). Die geeft de som van de getallen in de lijst L. Gebruik geen sum.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
Hint
Het eerste element is L[0] en de rest is L[1:], net als bij een string. Dit is de strategie van de dieven in opdracht 3 van het eerste college: tel je eigen getal op bij de som van de rest.
# jouw oplossing
assert sum_list([2, 6, 9]) == 17
assert sum_list([4]) == 4
assert sum_list([]) == 0
Opdracht 7¶
Schrijf de functie double_letters(s). Die geeft de string s met elk teken twee keer.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
Hint
s[0] * 2 is het eerste teken twee keer.
# jouw oplossing
assert double_letters("hi") == "hhii"
assert double_letters("hallo") == "hhaalllloo"
assert double_letters("") == ""
Opdracht 8¶
Schrijf de functie no_x(s). Die geeft de string s zonder de x’en.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
Hint
Net als keepvwl uit het tweede college: hou het eerste teken, of laat het weg.
# jouw oplossing
assert no_x("x1xx2x3") == "123"
assert no_x("xxx") == ""
assert no_x("") == ""
Opdracht 9¶
Schrijf de functie divisible_by(n, L). Die geeft een lijst met de getallen uit L die deelbaar zijn door n, in dezelfde volgorde.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
Hint
Je bouwt een lijst op. Hou je het eerste element, dan plak je [L[0]] voor het antwoord op de rest.
# jouw oplossing
assert divisible_by(5, [15, 0, 23, 4]) == [15, 0]
assert divisible_by(3, [2, 4, 8, 10]) == []
assert divisible_by(2, []) == []
Opdracht 10¶
Schrijf de functie all_star(s). Die geeft de string s met een * tussen elk paar tekens.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
Hint
Achter het laatste teken komt geen *. Een string met hoogstens één teken is dus het basisgeval: len(s) <= 1.
# jouw oplossing
assert all_star("hallo") == "h*a*l*l*o"
assert all_star("hi") == "h*i"
assert all_star("a") == "a"
assert all_star("") == ""
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
ngelijk aan 0, dan geef jeTrueterug.Is een van de twee woorden leeg, dan geef je
Falseterug.Is de laatste letter van het ene woord niet gelijk aan de laatste letter van het andere, dan geef je
Falseterug.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 |
|---|---|
|
|
|
|
|
|
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 |
|---|---|
|
|
|
|
|
|
Hint
De recursieve versie heeft dezelfde vorm als divisible_by 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([]) == []