Recursie¶

Deze pagina bevat uitvoerbare code.

Gebruik recursie om de volgende problemen op te lossen. Bedenk bij elke functie eerst wat het basisgeval is, en met welk kleiner probleem je de recursieve aanroep doet.

Werk lokaal in VS Code:

Begin met een schone kernel: herstart de kernel om eerder uitgevoerde code te wissen.
Vul bij elke opdracht de startcel in en voer die uit.
Voer daarna de testcel direct eronder uit. Als alle assertions slagen, verschijnt er geen uitvoer. Een AssertionError betekent dat je resultaat bij een test afwijkt van de verwachte waarde; controleer dan je functie.

De oplossingen onderaan gebruiken dezelfde functienamen. Heb je die uitgevoerd, herstart dan de kernel voordat je je eigen code opnieuw uitvoert en test.

Opgaven¶

Opdracht 1: `one_to_sum`¶

De functie one_to_sum(n) geeft de som van de getallen 1 tot en met n terug. Gebruik geen sum.

def one_to_sum(n):
    """Geeft de som van de getallen 1 tot en met n."""
    ...

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

Opdracht 2: `sum_list`¶

De functie sum_list(L) geeft de som van de getallen in de lijst L terug. Gebruik geen sum.

def sum_list(L):
    """Geeft de som van de getallen in L."""
    ...

assert sum_list([2, 6, 9]) == 17
assert sum_list([4]) == 4
assert sum_list([]) == 0

Opdracht 3: `mult_of_five`¶

De functie mult_of_five(n) geeft een lijst met de eerste n veelvouden van 5 terug: 5, 10, 15, enzovoort.

def mult_of_five(n):
    """Geeft een lijst met de eerste n veelvouden van 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]

Opdracht 4: `power_n`¶

De functie power_n(b, n) geeft b tot de macht n terug. Ga ervan uit dat b en n 0 of groter zijn, en gebruik geen **.

def power_n(b, n):
    """Geeft b tot de macht n."""
    ...

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

Opdracht 5: `double_letters`¶

De functie double_letters(s) geeft de string s terug met elk teken twee keer.

def double_letters(s):
    """Geeft s terug met elk teken twee keer."""
    ...

assert double_letters("hi") == "hhii"
assert double_letters("hello") == "hheelllloo"

Opdracht 6: `no_x`¶

De functie no_x(s) geeft de string s terug zonder de x’en.

def no_x(s):
    """Geeft s terug zonder de x'en."""
    ...

assert no_x("x1xx2x3") == "123"
assert no_x("xxx") == ""

Opdracht 7: `all_star`¶

De functie all_star(s) geeft de string s terug met een * tussen elk paar tekens.

def all_star(s):
    """Geeft s terug met een * tussen elk paar tekens."""
    ...

assert all_star("hello") == "h*e*l*l*o"
assert all_star("hi") == "h*i"
assert all_star("") == ""

Opdracht 8: `divisible_by`¶

De functie divisible_by(n, L) geeft een lijst terug met de getallen uit L die deelbaar zijn door n.

def divisible_by(n, L):
    """Geeft een lijst met de getallen uit L die deelbaar zijn door n."""
    ...

assert divisible_by(5, [15, 0, 23, 4]) == [15, 0]
assert divisible_by(3, [2, 4, 8, 10]) == []
assert divisible_by(2, []) == []

Opdracht 9: `starts_with`¶

De functie starts_with(s, L) geeft een lijst terug met de strings uit L die beginnen met s. Gebruik niet de stringmethode startswith.

def starts_with(s, L):
    """Geeft een lijst met de strings uit L die beginnen met s."""
    ...

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"]) == []

Opdracht 10: `end_x`¶

De functie end_x(s) geeft de string s terug met alle x’en verplaatst naar het einde.

def end_x(s):
    """Geeft s terug met alle x'en verplaatst naar het einde."""
    ...

assert end_x("abxyz") == "abyzx"
assert end_x("xxabc") == "abcxx"
assert end_x("abc") == "abc"

Opdracht 11: `ngram`¶

Hoe vaak een letter voorkomt, is een kenmerk van een taal. Om tekens te tellen breek je woorden op in opeenvolgende tekens, zogenaamde n-grams (zie ook Wikipedia en bijvoorbeeld de Google Books Ngram Viewer). Gaat het om één teken, dan heet dat een unigram. Langere reeksen geven meer informatie, zoals een bigram of een trigram: twee of drie opeenvolgende tekens.

De functie ngram(w, n) geeft een lijst terug met alle delen van n opeenvolgende tekens uit het woord w.

def ngram(w, n):
    """Geeft een lijst met alle delen van n opeenvolgende tekens uit het woord w."""
    ...

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"]

Uitwerkingen¶

Opdracht 1: `one_to_sum`¶

def one_to_sum(n):
    """Geeft de som van de getallen 1 tot en met 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  # 3 + 2 + 1
assert one_to_sum(5) == 15  # 5 + 4 + 3 + 2 + 1

Opdracht 2: `sum_list`¶

def sum_list(L):
    """Geeft de som van de getallen 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

Opdracht 3: `mult_of_five`¶

def mult_of_five(n):
    """Geeft een lijst met de eerste n veelvouden van 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]

Opdracht 4: `power_n`¶

def power_n(b, n):
    """Geeft b tot de macht 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

Opdracht 5: `double_letters`¶

def double_letters(s):
    """Geeft s terug met elk teken twee keer."""
    if len(s) == 0:
        return ""
    else:
        return s[0] * 2 + double_letters(s[1:])

assert double_letters("hi") == "hhii"
assert double_letters("hello") == "hheelllloo"

Opdracht 6: `no_x`¶

def no_x(s):
    """Geeft s terug zonder de x'en."""
    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") == ""

Opdracht 7: `all_star`¶

def all_star(s):
    """Geeft s terug met een * tussen elk paar tekens."""
    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("") == ""

Opdracht 8: `divisible_by`¶

def divisible_by(n, L):
    """Geeft een lijst met de getallen uit L die deelbaar zijn door 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, []) == []

Opdracht 9: `starts_with`¶

def starts_with(s, L):
    """Geeft een lijst met de strings uit L die beginnen met 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"]) == []

Opdracht 10: `end_x`¶

def end_x(s):
    """Geeft s terug met alle x'en verplaatst naar het einde."""
    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"

Opdracht 11: `ngram`¶

def ngram(w, n):
    """Geeft een lijst met alle delen van n opeenvolgende tekens uit het woord w."""
    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"]

Recursie¶

Opgaven¶

Opdracht 1: one_to_sum¶

Opdracht 2: sum_list¶

Opdracht 3: mult_of_five¶

Opdracht 4: power_n¶

Opdracht 5: double_letters¶

Opdracht 6: no_x¶

Opdracht 7: all_star¶

Opdracht 8: divisible_by¶

Opdracht 9: starts_with¶

Opdracht 10: end_x¶

Opdracht 11: ngram¶

Uitwerkingen¶

Opdracht 1: one_to_sum¶

Opdracht 2: sum_list¶

Opdracht 3: mult_of_five¶

Opdracht 4: power_n¶

Opdracht 5: double_letters¶

Opdracht 6: no_x¶

Opdracht 7: all_star¶

Opdracht 8: divisible_by¶

Opdracht 9: starts_with¶

Opdracht 10: end_x¶

Opdracht 11: ngram¶

Opdracht 1: `one_to_sum`¶

Opdracht 2: `sum_list`¶

Opdracht 3: `mult_of_five`¶

Opdracht 4: `power_n`¶

Opdracht 5: `double_letters`¶

Opdracht 6: `no_x`¶

Opdracht 7: `all_star`¶

Opdracht 8: `divisible_by`¶

Opdracht 9: `starts_with`¶

Opdracht 10: `end_x`¶

Opdracht 11: `ngram`¶

Opdracht 1: `one_to_sum`¶

Opdracht 2: `sum_list`¶

Opdracht 3: `mult_of_five`¶

Opdracht 4: `power_n`¶

Opdracht 5: `double_letters`¶

Opdracht 6: `no_x`¶

Opdracht 7: `all_star`¶

Opdracht 8: `divisible_by`¶

Opdracht 9: `starts_with`¶

Opdracht 10: `end_x`¶

Opdracht 11: `ngram`¶