Deze vraag staat op 6 punten. Je moet een recursief algoritme schrijven. Kies één van de 3 onderstaande opgaven die je programmeert. De gemakkelijkste oefening staat eerst, de moeilijkste laatst. Als je een moeilijkere oefening oplost krijg je wel meer punten.
Deze oefening verbetert zichzelf via Dodona. Je krijgt sowieso een rood kruisje, maar klik door op het tabblad van de oefening die jij indiende om te zien hoe je het deed.
Schrijf een functie macht(a, b) die recursie gebruikt om \(a^{b}\) uit te rekenen. Je functie mag géén ingebouwde machtsverheffing (zoals **) gebruiken.
Je mag ervan uitgaan dat a in alle testgevallen positief is.
Schrijf een functie combinaties(n, k) die recursie gebruikt om uit te rekenen op hoeveel manieren je k keuzes kan maken uit n elementen. Je mag ervan uitgaan dat in alle testgevallen:
Ter herhaling: een combinatie kun je berekenen via
\[\binom{n}{k}=\frac{n!}{k!\cdot(n-k)!}\]. Tip: denk aan de driehoek van Pascal om de recursieve definitie te vinden.
1
1 1
1 2 1
1 3 3 1
...
Binary Search is een zoekalgoritme dat een getal zoekt in een gesorteerde lijst. Het doet dit door telkens het middelpunt te zoeken, en te kijken of dit middelpunt groter, kleiner of gelijk aan het te zoeken getal is. Op die manier wordt in elke stap de helft van de lijst geëlimineerd.
Schrijf Binary Search recursief, met de volgende randvoorwaarden:
binary_search(lijst, getal, a, b). Hierbij geef je a en b, de minimale en maximale index van waar getal te zoeken is, mee als parameter.getal niet in lijst zit return je -1.Om je op weg te helpen krijg je ook al een niet-recursieve implementatie van dezelfde functie (zonder a en b als parameters):
def binary_search(lijst, getal):
a = 0
b = len(lijst) - 1
while a <= b:
c = (a + b) // 2
g = lijst[c]
if g == getal:
return c
if g > getal:
b = c - 1
continue
a = c + 1
if getal == lijst[a]:
return lijst[a]
return -1