Recursief ontwerpen

Recursief ontwerpen#

Zodra je een probleem recursief wil oplossen moet je twee belangrijke stappen maken.

  • Bepaal de base case. Dit voorkomt dat je in een oneindige recursie terecht komt

  • Bepaal de recursie case. Roept de functie opnieuw aan met een kleiner probleem.

Optelling: plusone(n)#

De functie plusone(n) telt n door 1-en op te tellen. Als n gelijk is aan 5 dan worden 5 1-en bij elkaar opgeteld. Hoe kan je dit recursief oplossen? Denk altijd eerst aan de base case, in welk geval is is geen recursie meer mogelijk?

Plan:#

Wat moet in dit geval voor de ... moeten worden ingevuld voor de base en recursieve case?

  • plusone(0) moet … teruggeven

recursie case:

  • plusone(5) is de waarde van 1+1+1+1+1 en is gelijk aan de waarde 1 + (...), wat gelijk is aan 1 + plusone(...)

programmeren#

def plusone(n):
    """Geeft n terug door 1-en op te tellen!
    """
    if n == 0:  # base case
        return ...
    else:       # recursive case
        return ...

De ... zie je hier in de code terug. Wat moet voor de base- en recursieve case worden ingevuld? Denk hier terug aan aan fac(x), hetzelfde patroon zal je hier moeten volgen!

Oplossing#

def plusone(n):
    """Geeft n terug door 1-en op te tellen!
    """
    if n == 0:  # base case
        return 0
    else:       # recursive case
        return 1 + plusone(n-1)

assert plusone(0) == 0  # test de base case
assert plusone(5) == 5  # test de oplossing

Machtverheffing: pow(b, p)#

De functie pow(b, p) met de positieve integers b en p berekent bp. Je mag de operator ** niet gebruiken en het moet recursief opgelost worden.

plan#

De base case:

pow(2, 0) moet … teruggeven

recursie case:

  • pow(2, 5) is de waarde van 2*2*2*2*2 en is gelijk aan

  • 2 * (...), wat gelijk is aan 2 * pow(..., ...)

Programmeren#

def pow(b, p):
    """b**p, recursief!
    """
    if p == 0:  # base case
        return ...
    else:       # recursive case
        return ...

Oplossing#

def pow(b, p):
    """b**p, recursief!
    """
    if p == 0:  # base case
        return 1.0
    else:       # recursive case
        return b * pow(b, p-1)

assert pow(2, 0) == 1.0   # test de base case
assert pow(2, 5) == 32.0  # test de oplossing

Aantal klinkers: vwl(s)#

De functie vwl(s) checkt hoeveel klinkers er in de string s zit en geeft dit aantal terug.

Python is in#

Bevind een element zich in een sequentie (een list, een string, …)?

Dit probleem zal je vaak gaan tegenkomen: bijvoorbeeld bij de vraag of “i” een klinker is? Klinkers zijn de karakters a, e, i, o en u. Dit kan je als een sequentie schrijven, bijvoorbeeld als string "aeiou" of als list ["a", "e", "i", "o", "u"]. Python kent de in operator om te testen of een element zich in een sequentie bevindt, bijvoorbeeld "i" in "aeiou". Een paar voorbeelden:

"i" in "team"

False

"i" in "alien"

True

3*"i" in "aliiien"

True

42 in [41, 42, 42]

True

42 in [[42], "42"]

False

"e" in "eaiou"

True

Plan#

De base case:

vwl("") moet … teruggeven

Recursieve case:
vwl("zaaiuien") is het aantal klinkers in “zaaiuien” en is gelijk aan het aantal klinkers in “z” + het aantal klinkers in vwl(...). Dus het wordt 1 + vwl(...) of 0 + vwl(...)

programmeren#

def vwl(s):
    """Tel het aantal klinkers in s
    """
    if s == "":
        ...
    elif ...:
        return ...
    else:
        return ...

def vwl(s):
    """Tel het aantal klinkers in s
    """
    if s == "":
        return 0
    elif s[0] in "aeiou":
        return 1 + vwl(s[1:])
    else:
        return vwl(s[1:])

vwl("zaaiuien")

6

Alleen klinkers#

Plan#

Base case:
keepvwl("") moet … teruggeven

Recursieve case:
keepvwl("pluto") is “pluto” zonder medeklinkers en is gelijk aan de klinkers in “p” + de klinkers in keepvwl(...). Als het een klinker is, bewaren we het. "p"+ keepvwl(...) als het geen klinker is, bewaren we het niet. ""+ keepvwl(...). Deze strategie wordt ook wel use it or loose it genoemd.

Programmeren#

def keepvwl(s):
    """Geef ALLEEN de klinkers in s terug
    """
    if s == "":
        return ...
    elif ...:
        return ...
    else:
        return ...

Oplossing#

def keepvwl(s):
    """Geef ALLEEN de klinkers in s terug
    """
    if s == "":
        return ""
    elif s[0] in "aeiou":
        return s[0] + keepvwl(s[1:])
    else:
        return keepvwl(s[1:])

keepvwl("pluto")

'uo'

Opgave: 1#

De functie max(L) geeft de grootste waarde van L terug

Plan#

Base case:
als len(L) == 1 dan moet max(L) … teruggeven

Recursieve case
max([7, 5, 9, 2]) geeft het hoogste getal terug en is 7 of het hoogste getal in max(...)

Programmeren#

def max(L):
    """Geef de grootste waarde van L terug
    """
    if len(L) == 1:
        return ...
    
    M = ...  # De max van het RESTANT van L
    
    if ...:
        return ...
    else:
        return ...

Maak het bovenstaande programma af.

Opgave 2:#

De functie zeroest(L)geeft het getal terug in L dat het dichtst bij 0 ligt.

Plan:#

Base case:
als len(L) == 1 dan moet zeroest(L) … teruggeven

Recursieve case:
zeroest([-7, 5, 9, 2]) geeft getal het dichtst bij 0 terug en is -7 of het getal het dichtst bij 0 in zeroest(...)

Programmeren#

def zeroest(L):
    """Geef het getal in L het dichtst bij 0 terug
    """
    if len(L) == 1:
        return ...
    
    Z = ...  #  Getal dichtst bij 0 van de REST van L
    
    if ...:
        return ...
    else:
        return ...

Maak het bovenstaande programma af.

Opgave 3#

Schrijf de functie counting(L) dat van een lijst L de hoeveelheid elementen teruggeeft. Maak gebruik van recursie

Opdracht 4#

Schrijf de functie element_in(ele, lis) dat checkt of de variabele ele in de lijst lis zit. Zo ja, dan geeft het een trueterug, anders geeft het een falseterug. Maak gebruik van recursie