Recursief ontwerpen

Deze pagina bevat uitvoerbare code. Activeren

In het eerste college zag je hoe een recursieve functie werkt. In dit college ontwerp je er zelf een. Bij elke functie beantwoord je dezelfde drie vragen:

1. Wat is het basisgeval, en wat geeft de functie daar terug?

2. Wat is het kleinere probleem, waarvoor de functie zichzelf aanroept?

3. Hoe combineer je: hoe maak je van het antwoord op het kleinere probleem het antwoord op het hele probleem?

Elk voorbeeld begint met een plan met gaten (...). Vul de gaten eerst zelf in, op papier of in je hoofd, en kijk daarna naar de oplossing.

Machtsverheffen: power(b, p)

power(b, p) rekent \(b^p\) uit, voor een geheel getal p van 0 of groter, zonder de operator **.

Plan

• Basisgeval. power(2, 0) geeft ... terug.

• Kleiner probleem. power(2, 5) is 2 * 2 * 2 * 2 * 2. Na de eerste 2 * staat 2 * 2 * 2 * 2, en dat is power(..., ...).

• Combineren. power(2, 5) is 2 * power(..., ...).

Programmeren

def power(b, p):
    """Geeft b tot de macht p, voor een geheel getal p van 0 of groter."""
    if p == 0:  # basisgeval
        return ...
    else:  # recursief geval
        return ...

Oplossing

def power(b, p):
    """Geeft b tot de macht p, voor een geheel getal p van 0 of groter."""
    if p == 0:  # basisgeval
        return 1
    else:  # recursief geval
        return b * power(b, p - 1)


assert power(2, 0) == 1
assert power(2, 5) == 32
assert power(3, 2) == 9

def power(b, p): """Geeft b tot de macht p, voor een geheel getal p van 0 of groter.""" if p == 0: # basisgeval return 1 else: # recursief geval return b * power(b, p - 1) assert power(2, 0) == 1 assert power(2, 5) == 32 assert power(3, 2) == 9

Klinkers tellen: vwl(s)

vwl(s) geeft terug hoeveel klinkers er in de string s staan. Klinkers zijn a, e, i, o en u. Of een teken een klinker is, vraag je met de operator in, zoals in week 4 van Programmeren 1: s[0] in "aeiou".

Plan

• Basisgeval. vwl("") geeft ... terug.

• Kleiner probleem. Bij vwl("zaaiuien") is dat de rest na het eerste teken: vwl(...).

• Combineren. Is het eerste teken een klinker, dan is het antwoord 1 + vwl(...). Is het geen klinker, dan is het vwl(...).

Programmeren

def vwl(s):
    """Geeft het aantal klinkers in s."""
    if s == "":  # basisgeval
        return ...
    elif ...:  # recursief geval: het eerste teken is een klinker
        return ...
    else:  # recursief geval: het eerste teken is geen klinker
        return ...

Oplossing

def vwl(s):
    """Geeft het aantal klinkers in s."""
    if s == "":  # basisgeval
        return 0
    elif s[0] in "aeiou":  # recursief geval: het eerste teken is een klinker
        return 1 + vwl(s[1:])
    else:  # recursief geval: het eerste teken is geen klinker
        return vwl(s[1:])


assert vwl("") == 0
assert vwl("zaaiuien") == 6

def vwl(s): """Geeft het aantal klinkers in s.""" if s == "": # basisgeval return 0 elif s[0] in "aeiou": # recursief geval: het eerste teken is een klinker return 1 + vwl(s[1:]) else: # recursief geval: het eerste teken is geen klinker return vwl(s[1:]) assert vwl("") == 0 assert vwl("zaaiuien") == 6

Deze functie heeft twee recursieve gevallen. In allebei is het kleinere probleem hetzelfde, s[1:]; alleen het combineren verschilt.

Alleen de klinkers: keepvwl(s)

keepvwl(s) geeft een string terug met alleen de klinkers uit s, in dezelfde volgorde. Het antwoord is nu een string en geen getal.

Plan

• Basisgeval. keepvwl("") geeft ... terug.

• Kleiner probleem. Bij keepvwl("pluto") is dat keepvwl(...).

• Combineren. Is het eerste teken een klinker, dan hou je het: ... + keepvwl(...). Is het geen klinker, dan laat je het weg: keepvwl(...).

Programmeren

def keepvwl(s):
    """Geeft alleen de klinkers uit s, in dezelfde volgorde."""
    if s == "":  # basisgeval
        return ...
    elif ...:  # recursief geval: hou het eerste teken
        return ...
    else:  # recursief geval: laat het eerste teken weg
        return ...

Oplossing

def keepvwl(s):
    """Geeft alleen de klinkers uit s, in dezelfde volgorde."""
    if s == "":  # basisgeval
        return ""
    elif s[0] in "aeiou":  # recursief geval: hou het eerste teken
        return s[0] + keepvwl(s[1:])
    else:  # recursief geval: laat het eerste teken weg
        return keepvwl(s[1:])


assert keepvwl("") == ""
assert keepvwl("pluto") == "uo"

def keepvwl(s): """Geeft alleen de klinkers uit s, in dezelfde volgorde.""" if s == "": # basisgeval return "" elif s[0] in "aeiou": # recursief geval: hou het eerste teken return s[0] + keepvwl(s[1:]) else: # recursief geval: laat het eerste teken weg return keepvwl(s[1:]) assert keepvwl("") == "" assert keepvwl("pluto") == "uo"

Het grootste getal: largest(L)

largest(L) geeft het grootste getal uit de lijst L terug. Python heeft daar zelf al een functie voor, max; daarom heet deze largest. Een lege lijst heeft geen grootste getal, dus L is nooit leeg.

Plan

• Basisgeval. Een lijst met één getal: largest([7]) geeft ... terug.

• Kleiner probleem. Bij largest([7, 5, 9, 2]) is dat het grootste getal in de rest: largest(...).

• Combineren. Het antwoord is 7 of het grootste getal in de rest, afhankelijk van welke van de twee groter is.

Programmeren

def largest(L):
    """Geeft het grootste getal uit L; L is niet leeg."""
    if len(L) == 1:  # basisgeval
        return ...

    rest = ...  # het grootste getal in de rest van L

    if ...:
        return ...
    else:
        return ...

Oplossing

def largest(L):
    """Geeft het grootste getal uit L; L is niet leeg."""
    if len(L) == 1:  # basisgeval
        return L[0]

    rest = largest(L[1:])  # het grootste getal in de rest van L

    if L[0] > rest:
        return L[0]
    else:
        return rest


assert largest([7]) == 7
assert largest([7, 5, 9, 2]) == 9
assert largest([-3, -8]) == -3

def largest(L): """Geeft het grootste getal uit L; L is niet leeg.""" if len(L) == 1: # basisgeval return L[0] rest = largest(L[1:]) # het grootste getal in de rest van L if L[0] > rest: return L[0] else: return rest assert largest([7]) == 7 assert largest([7, 5, 9, 2]) == 9 assert largest([-3, -8]) == -3

Hier zie je rest = ... uit het eerste college terug. De functie vergelijkt het eerste element met het antwoord op de rest, en dat antwoord moet er eerst zijn. Het is de strategie van de dieven in opdracht 1 van het eerste college: elke dief vergelijkt zijn eigen getal met het hoogste getal van de rest.

Vanaf het eind: strip_end(s)

Het kleinere probleem hoeft niet de rest ná het eerste teken te zijn. Soms kijk je naar het laatste teken, s[-1], en naar alles ervóór, s[:-1].

Wie iets intypt, zet er soms per ongeluk spaties achter. strip_end(s) geeft s terug zonder de spaties aan het eind. Spaties aan het begin blijven staan.

Plan

• Basisgeval. Hier zijn er twee. strip_end("") geeft ... terug. En is het laatste teken geen spatie, dan is er niets meer weg te halen: de functie geeft ... terug.

• Kleiner probleem. Is het laatste teken een spatie, dan is dat strip_end(...): de string zonder dat laatste teken.

• Combineren. Er valt niets te combineren. Het antwoord op het kleinere probleem is meteen het antwoord.

Programmeren

def strip_end(s):
    """Geeft s zonder de spaties aan het eind."""
    if s == "":  # basisgeval
        return ...
    elif ...:  # recursief geval: het laatste teken is een spatie
        return ...
    else:  # basisgeval: het laatste teken is geen spatie
        return ...

Oplossing

def strip_end(s):
    """Geeft s zonder de spaties aan het eind."""
    if s == "":  # basisgeval
        return ""
    elif s[-1] == " ":  # recursief geval: het laatste teken is een spatie
        return strip_end(s[:-1])
    else:  # basisgeval: het laatste teken is geen spatie
        return s


assert strip_end("") == ""
assert strip_end("hallo  ") == "hallo"
assert strip_end("  hallo") == "  hallo"
assert strip_end("   ") == ""

def strip_end(s): """Geeft s zonder de spaties aan het eind.""" if s == "": # basisgeval return "" elif s[-1] == " ": # recursief geval: het laatste teken is een spatie return strip_end(s[:-1]) else: # basisgeval: het laatste teken is geen spatie return s assert strip_end("") == "" assert strip_end("hallo ") == "hallo" assert strip_end(" hallo") == " hallo" assert strip_end(" ") == ""

Zodra het laatste teken geen spatie is, stopt de recursie. De rest van de string bekijkt de functie niet meer.

Stoppen zodra je het weet: only_digits(s)

only_digits(s) geeft True terug als s alleen uit cijfers bestaat, en anders False. Zo kun je nagaan of een pincode wel een getal is. Net als find_forty_two uit het eerste college stopt deze functie zodra ze het antwoord weet.

Plan

• Basisgeval. only_digits("") geeft ... terug: in een lege string staat geen teken dat geen cijfer is. En is het eerste teken geen cijfer, dan weet je het antwoord al: ....

• Kleiner probleem. Is het eerste teken wel een cijfer, dan hangt het af van de rest: only_digits(...).

• Combineren. Het antwoord op de rest is het antwoord op het geheel.

Programmeren

def only_digits(s):
    """Geeft True als s alleen uit cijfers bestaat."""
    if s == "":  # basisgeval
        return ...
    elif ...:  # basisgeval: het eerste teken is geen cijfer
        return ...
    else:  # recursief geval
        return ...

Oplossing

def only_digits(s):
    """Geeft True als s alleen uit cijfers bestaat."""
    if s == "":  # basisgeval
        return True
    elif s[0] not in "0123456789":  # basisgeval: het eerste teken is geen cijfer
        return False
    else:  # recursief geval
        return only_digits(s[1:])


assert only_digits("2026") == True
assert only_digits("20x6") == False
assert only_digits("") == True

def only_digits(s): """Geeft True als s alleen uit cijfers bestaat.""" if s == "": # basisgeval return True elif s[0] not in "0123456789": # basisgeval: het eerste teken is geen cijfer return False else: # recursief geval return only_digits(s[1:]) assert only_digits("2026") == True assert only_digits("20x6") == False assert only_digits("") == True

Opdrachten

Beantwoord bij elke opdracht eerst de drie vragen: wat is het basisgeval, wat is het kleinere probleem, en hoe combineer je? Schrijf daarna de functie, en voer de testcel uit.

Opdracht 1

zeroest(L) geeft het getal uit L terug dat het dichtst bij 0 ligt. L is niet leeg. De vorm is dezelfde als die van largest.

Aanroep	Resultaat
zeroest([-7, 5, 9, 2])	2
zeroest([-7, 5, -1, 9])	-1
zeroest([4])	4

Hint

Hoe ver een getal van 0 ligt, is zijn absolute waarde: abs(-7) is 7.

def zeroest(L):
    """Geeft het getal uit L dat het dichtst bij 0 ligt; L is niet leeg."""
    if len(L) == 1:  # basisgeval
        return ...

    rest = ...  # het getal in de rest van L dat het dichtst bij 0 ligt

    if ...:
        return ...
    else:
        return ...

def zeroest(L): """Geeft het getal uit L dat het dichtst bij 0 ligt; L is niet leeg.""" if len(L) == 1: # basisgeval return ... rest = ... # het getal in de rest van L dat het dichtst bij 0 ligt if ...: return ... else: return ...

assert zeroest([-7, 5, 9, 2]) == 2
assert zeroest([-7, 5, -1, 9]) == -1
assert zeroest([4]) == 4

assert zeroest([-7, 5, 9, 2]) == 2 assert zeroest([-7, 5, -1, 9]) == -1 assert zeroest([4]) == 4

Opdracht 2

Schrijf de functie counting(L), die het aantal elementen van de lijst L teruggeeft. Gebruik geen len. Dit is de vraag van de geblinddoekte dieven in opdracht 2 van het eerste college.

Aanroep	Resultaat
counting(["de", "vuurtoren", "draait"])	3
counting([])	0

# jouw oplossing

# jouw oplossing

assert counting([]) == 0
assert counting([42]) == 1
assert counting(["de", "vuurtoren", "draait"]) == 3

assert counting([]) == 0 assert counting([42]) == 1 assert counting(["de", "vuurtoren", "draait"]) == 3

Opdracht 3

Schrijf de functie element_in(x, L), die True teruggeeft als x een element van de lijst L is, en anders False. Gebruik geen in.

Aanroep	Resultaat
element_in(42, [41, 42, 43])	True
element_in(42, [])	False

Hint

Deze functie lijkt op find_forty_two uit het eerste college.

# jouw oplossing

# jouw oplossing

assert element_in(42, [41, 42, 43]) == True
assert element_in(42, []) == False
assert element_in("i", ["team"]) == False

assert element_in(42, [41, 42, 43]) == True assert element_in(42, []) == False assert element_in("i", ["team"]) == False

Opdracht 4

De grootste gemene deler (ggd) van twee getallen is het grootste getal waardoor ze allebei deelbaar zijn. Het algoritme van Euclides vindt hem zo:

• Is b gelijk aan 0, dan is de ggd van a en b gelijk aan a.

• Anders is de ggd van a en b gelijk aan de ggd van b en a % b.

Het kleinere probleem is hier geen rest van een lijst of een string, maar een kleiner paar getallen. Zo vind je de ggd van 1140 en 900:

Aanroep	a % b
gcd(1140, 900)	240
gcd(900, 240)	180
gcd(240, 180)	60
gcd(180, 60)	0
gcd(60, 0)	basisgeval: de ggd is 60

Schrijf de functie gcd(a, b) volgens dit algoritme.

# jouw oplossing

# jouw oplossing

assert gcd(1140, 900) == 60
assert gcd(900, 1140) == 60
assert gcd(7, 5) == 1
assert gcd(12, 0) == 12

assert gcd(1140, 900) == 60 assert gcd(900, 1140) == 60 assert gcd(7, 5) == 1 assert gcd(12, 0) == 12

Tot slot

Elke functie in dit college had een basisgeval, één recursieve aanroep op een kleiner probleem, en een manier om het antwoord daarop te combineren. De drie vragen werken voor elke recursieve functie die je deze week schrijft.

Vooruitblik: kan ik dit bedrag precies betalen?

In je portemonnee zitten drie munten: 20 cent, 50 cent en nog eens 50 cent. Kun je precies 70 cent betalen? En 80 cent?

Bij elke munt heb je een keuze: je gebruikt hem, of je gebruikt hem niet. Met één recursieve aanroep, zoals in dit college, kom je er niet: je moet beide keuzes uitproberen. Hoe dat gaat, leer je in week 4 van Programmeren 2. Je hoeft het nu niet te schrijven, maar bedenk alvast hoe je het zou aanpakken.