Recursie#
Gebruik recursie om de volgende problemen op te lossen.
Opgaven#
one_to_sum#
De functie one_to_sum accepteert een integer n en heeft als resultaat de optelling van de getallen 1 tot en met n. Je mag hier niet de ingebouwde functie sum gebruiken.
def one_to_sum(n):
"""Sum all integer values from 1 to n
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert one_to_sum(0) == 0
assert one_to_sum(1) == 1
assert one_to_sum(3) == 6 # 3 + 2 + 1
assert one_to_sum(5) == 15 # 5 + 4 + 3 + 2 + 1
sum_list#
De functie sum_list accepteert een list L met integers en heeft als resultaat de optelling van deze waarden. Je mag hier niet de ingebouwde funtie sum gebruiken.
def sum_list(L):
"""Sum all values in L
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert sum_list([2, 6, 9]) == 17
assert sum_list([4]) == 4
assert sum_list([]) == 0
mult_of_five#
De functie mult_of_five accepteert een integer n en heeft als resultaat een list met de veelvouden 1 tot en met n van 5.
def mult_of_five(n):
"""Return a list containing the first n multiples of 5
"""
...
Gebruik de volgende assertions om jow oplossingen te testen:
assert mult_of_five(0) == []
assert mult_of_five(1) == [5]
assert mult_of_five(2) == [5, 10]
assert mult_of_five(3) == [5, 10, 15]
power_n#
De functie power_n accepteert de integers b en n en heeft als resultaat b tot de machtn. Ga er van uit dat zowel b als n groter zijn dan 0, je mag hier niet ** gebruiken om het resultaat te berekenen.
def power_n(b, n):
"""Return base b to the power of n
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert power_n(0, 0) == 1
assert power_n(0, 1) == 0
assert power_n(1, 1) == 1
assert power_n(2, 2) == 4
assert power_n(2, 3) == 8
assert power_n(3, 2) == 9
double_letters#
De functie double_letters accepteert een string s en heeft als resulaat een string met de karakters in s verdubbeld.
def double_letters(s):
"""Double all letters in s
"""
...
Gebruik de volgende assertions om jouw oplossingen te testen:
assert double_letters("hi") == "hhii"
assert double_letters("hello") == "hheelllloo"
no_x#
De functie no_x accepteert een string s en verwijdert alle x’en geeft het resultaat terug.
def no_x(s):
"""Return s with all x's removed
"""
...
Gebruik de volgende assertions om jouw code te testen:
assert no_x("x1xx2x3") == "123"
assert no_x("xxx") == ""
all_star#
De functie all_star accepteert een string s en plaatst een * tussen de karakters en geeft het resultaat terug.
def all_star(s):
"""Returns string s with all characters separated by *
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert all_star("hello") == "h*e*l*l*o"
assert all_star("hi") == "h*i"
assert all_star("") == ""
divisible_by#
De functie divisible_by accepteert een integer n en een list L en geeft als resultaat een list terug met alle waarden in L deelbaar door n.
def divisible_by(n, L):
"""Return a list with values in L divisible by n
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert divisible_by(5, [15, 0, 23, 4]) == [15, 0]
assert divisible_by(3, [2, 4, 8, 10]) == []
assert divisible_by(2, []) == []
starts_with#
De functie starts_with accepteer een string s en een list met string L en heeft als resultaat een list met alle waarden in L die beginnen met s. Je mag hier niet de ingebouwde string methode startswith gebruiken.
def starts_with(s, L):
"""Return all strings in L which start with s
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert starts_with("a", []) == []
assert starts_with("a", ["bbc", "brits", "omroep"]) == []
assert starts_with("a", ["abc", "cde", "aha", "abba"]) == ["abc", "aha", "abba"]
assert starts_with("ab", ["abc", "cde", "aha", "abba"]) == ["abc", "abba"]
assert starts_with("abc", ["abc", "cde", "aha", "abba"]) == ["abc"]
assert starts_with("abcd", ["abc", "cde", "aha", "abba"]) == []
end_x#
De functie end_x accepteert een string s verplaatst alle x’en naar het einde van de string en geeft dit terug als resultaat.
def end_x(s):
"""Returns s with all x's moved to the end
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert end_x("abxyz") == "abyzx"
assert end_x("xxabc") == "abcxx"
assert end_x("abc") == "abc"
ngram#
De kans dat een letter wordt gebruikt is een maat voor een taal. Om karakters te tellen in tekst moeten woorden worden opgebroken in opeenvolgende karakters, zogenaamde n-grams (zie ook Wikipedia en bijvoorbeeld Google Books Ngram Viewer). In het geval van een enkel karakter spreek je van een unigram, langere opeenvolgingen geven meer informatie, bijvoorbeeld een bi- of trigram (twee of drie opeenvolgende karakters).
De functie ngram accepteert een string w en een integer n en geeft een lijst terug met n opeenvolgende delen van een woord w.
def ngram(w, n):
"""Break up a word w into n consecutive parts
"""
...
Gebruik de volgende assertions om jouw oplossing te testen:
assert ngram("alien", 1) == ["a", "l", "i", "e", "n"] # 1-gram (unigram)
assert ngram("alien", 2) == ["al", "li", "ie", "en"] # 2-gram (bigram)
assert ngram("alien", 3) == ["ali", "lie", "ien"] # 3-gram (trigram)
assert ngram("alien", 4) == ["alie", "lien"]
assert ngram("alien", 5) == ["alien"]
Oplossingen#
one_to_sum#
def one_to_sum(n):
"""Sum all integer values from 1 to n
"""
if n == 0:
return 0
else:
return n + one_to_sum(n - 1)
assert one_to_sum(0) == 0
assert one_to_sum(1) == 1
assert one_to_sum(3) == 6 # 1 + 2 + 3
assert one_to_sum(5) == 15 # 1 + 2 + 3 + 4 + 5
sum_list#
def sum_list(L):
"""Sum all values in L
"""
if len(L) == 0:
return 0
else:
return L[0] + sum_list(L[1:])
assert sum_list([2, 6, 9]) == 17
assert sum_list([4]) == 4
assert sum_list([]) == 0
mult_of_five#
def mult_of_five(n):
"""Return a list containing the first n multiples of 5
"""
if n == 0:
return []
else:
return mult_of_five(n - 1) + [n * 5]
assert mult_of_five(0) == []
assert mult_of_five(1) == [5]
assert mult_of_five(2) == [5, 10]
assert mult_of_five(3) == [5, 10, 15]
power_n#
def power_n(b, n):
"""Return base b to the power of n
"""
if n == 0:
return 1
else:
return b * power_n(b, n - 1)
assert power_n(0, 0) == 1
assert power_n(0, 1) == 0
assert power_n(1, 1) == 1
assert power_n(2, 2) == 4
assert power_n(2, 3) == 8
assert power_n(3, 2) == 9
double_letters#
def double_letters(s):
"""Double all letters in s
"""
if len(s) == 0:
return ""
else:
return s[0] * 2 + double_letters(s[1:])
assert double_letters("hi") == "hhii"
assert double_letters("hello") == "hheelllloo"
no_x#
def no_x(s):
"""Return s with all x's removed
"""
if len(s) == 0:
return ""
elif s[0] == "x":
return no_x(s[1:])
else:
return s[0] + no_x(s[1:])
assert no_x("x1xx2x3") == "123"
assert no_x("xxx") == ""
all_star#
def all_star(s):
"""Returns string s with all characters separated by *.
"""
if len(s) <= 1:
return s
else:
return s[0] + "*" + all_star(s[1:])
assert all_star("hello") == "h*e*l*l*o"
assert all_star("hi") == "h*i"
assert all_star("") == ""
divisible_by#
def divisible_by(n, L):
"""Return a list with values in L divisible by n
"""
if len(L) == 0:
return []
elif L[0] % n == 0:
return [L[0]] + divisible_by(n, L[1:])
else:
return divisible_by(n, L[1:])
assert divisible_by(5, [15, 0, 23, 4]) == [15, 0]
assert divisible_by(3, [2, 4, 8, 10]) == []
assert divisible_by(2, []) == []
starts_with#
def starts_with(s, L):
"""Return all strings in L which start with s
"""
if len(L) == 0:
return []
elif s == L[0][:len(s)]:
return [L[0]] + starts_with(s, L[1:])
else:
return starts_with(s, L[1:])
assert starts_with("a", []) == []
assert starts_with("a", ["bbc", "brits", "omroep"]) == []
assert starts_with("a", ["abc", "cde", "aha", "abba"]) == ["abc", "aha", "abba"]
assert starts_with("ab", ["abc", "cde", "aha", "abba"]) == ["abc", "abba"]
assert starts_with("abc", ["abc", "cde", "aha", "abba"]) == ["abc"]
assert starts_with("abcd", ["abc", "cde", "aha", "abba"]) == []
end_x#
def end_x(s):
"""Returns s with all x's moved to the end
"""
if len(s) <= 1:
return s
elif s[0] == "x":
return end_x(s[1:]) + s[0]
else:
return s[0] + end_x(s[1:])
assert end_x("abxyz") == "abyzx"
assert end_x("xxabc") == "abcxx"
assert end_x("abc") == "abc"
ngram#
def ngram(w, n):
"""Break up a word w into n consecutive parts
"""
if len(w) < n:
return []
else:
return [w[:n]] + ngram(w[1:], n)
assert ngram("alien", 1) == ["a", "l", "i", "e", "n"] # 1-gram (unigram)
assert ngram("alien", 2) == ["al", "li", "ie", "en"] # 2-gram (bigram)
assert ngram("alien", 3) == ["ali", "lie", "ien"] # 3-gram (trigram)
assert ngram("alien", 4) == ["alie", "lien"]
assert ngram("alien", 5) == ["alien"]