Recursie in Python
Recursie in Python
Open bij de voorkennis van leerlingen: ze kennen functies, if-statements en lussen al. Positioneer recursie als een andere manier om herhaling en opbouw te beschrijven.
Lesdoel
Ik kan uitleggen wat recursie is en een eenvoudige recursieve functie in Python lezen en schrijven.
Deze slide heeft geen instructies
Welke woorden of ideeën koppel jij aan recursie?
Gebruik deze woordwolk om voorkennis zichtbaar te maken. Verwachte input: functies, zichzelf aanroepen, herhaling, lus, stap voor stap, stopvoorwaarde, kleiner probleem.
Wat is recursie?
Recursie is een techniek waarbij een functie zichzelf aanroept.
Dat werkt alleen goed als het probleem steeds wordt teruggebracht tot een kleiner probleem van hetzelfde type.
Benadruk dat recursie geen magische herhaling is: elke aanroep moet dichter bij een stopmoment komen.
De twee vaste onderdelen
Basiscase: het eenvoudige geval waarbij de functie direct stopt
Recursieve stap: de functie roept zichzelf aan met een kleinere invoer
Zonder basiscase blijft de functie doorgaan
Gebruik de termen basiscase en recursieve stap consequent in de hele les.
Hoe een recursieve functie werkt
Een recursieve functie volgt meestal deze structuur:
```python
def functie(x):
if eenvoudige_situatie:
return antwoord
else:
return functie(kleinereversievan_x)
```
De invoer moet dus bij elke stap eenvoudiger worden.
Wijs op de overeenkomst met if/else die leerlingen al kennen. Nieuw is alleen dat de functie zichzelf mag aanroepen.
Voorbeeld: aftellen
```python
def tel_af(n):
if n == 0:
print("start")
else:
print(n)
tel_af(n - 1)
```
Hier wordt `n` bij elke stap kleiner, tot de basiscase `n == 0`.
Dit is een laagdrempelig eerste voorbeeld zonder returnwaarde. Laat leerlingen voorspellen wat er geprint wordt bij tel_af(3).
Stap voor stap gelezen
Bij `tel_af(3)` gebeurt dit:
`telaf(3)` → print `3` → `telaf(2)`
`telaf(2)` → print `2` → `telaf(1)`
`telaf(1)` → print `1` → `telaf(0)`
`tel_af(0)` → print `start` en stop
Maak expliciet dat elke functieaanroep pas klaar is nadat de volgende aanroep is uitgevoerd.
Wat is noodzakelijk voor werkende recursie?
Een kleiner probleem
Een for-lus
Een globale variabele
Een print-opdracht
Toetst de kern uit slides 2–4: recursie werkt alleen als het probleem wordt teruggebracht tot een kleinere versie van hetzelfde type.
Vul de kernbegrippen in
Bij recursie roept een functie zichzelf aan. Een goede recursieve functie heeft een duidelijke basiscase en een recursieve stap waarbij de invoer kleiner wordt.
Herneemt de vaste termen uit slides 2–4 in een betekenisvolle context.
Wat print tel_af(2)?
Bespreek dat de uitvoer regel voor regel is: 2, 1, start. Belangrijk: de basiscase print alleen 'start' en stopt daarna.
Recursie met returnwaarde
Recursie wordt krachtiger als een functie niet alleen iets uitvoert, maar ook een waarde teruggeeft.
Dan bouwt elke functieaanroep verder op het resultaat van de volgende aanroep.
Dit is de overgang van procedureel voorbeeld naar berekenend voorbeeld.
Voorbeeld: faculteit
De faculteit van een getal is het product van alle positieve gehele getallen tot en met dat getal.
```python
def faculteit(n):
if n == 0:
return 1
else:
return n * faculteit(n - 1)
```
Bij elke stap wordt het probleem kleiner: `faculteit(4)` gebruikt `faculteit(3)`.
Noem kort dat 0! = 1 per definitie, zodat de basiscase logisch blijft.
Faculteit uitgewerkt
```python
faculteit(4)
= 4 * faculteit(3)
= 4 3 faculteit(2)
= 4 3 2 * faculteit(1)
= 4 3 2 1 faculteit(0)
= 4 3 2 1 1
= 24
```
Leg uit dat de berekening eerst steeds dieper gaat en pas daarna wordt uitgerekend bij het terugkeren.
De call stack
Elke functieaanroep wordt tijdelijk onthouden
Python bewaart waar de functie later verder moet
Bij recursie ontstaat zo een stapel van aanroepen
De laatste aanroep wordt als eerste afgehandeld
Verbind dit met het vorige faculteitsvoorbeeld: de stack groeit tijdens het afdalen en krimpt tijdens het terugkeren.
Waarom werkt dat?
Bij `return n * faculteit(n - 1)` moet Python eerst weten wat `faculteit(n - 1)` oplevert.
Daarom wacht elke aanroep op de volgende. Pas wanneer de basiscase is bereikt, kunnen de openstaande berekeningen één voor één worden afgerond.
Deze slide heeft geen instructies
Waarom kan Python faculteit(4) pas afronden na faculteit(0)?
Door de for-lus
Door de printvolgorde
Door de open berekeningen
Door een globale teller
Sluit aan op slides 7–11: bij 'return n * faculteit(n - 1)' moet Python eerst de diepere aanroep kennen voordat de eerdere berekening af kan worden gemaakt.
Vul de uitleg aan
Bij faculteit wacht elke aanroep op de volgende. Python bewaart die actieve functies op de call stack. Pas bij de basiscase kunnen de berekeningen worden afgerond.
Controleert of leerlingen de relatie tussen functieaanroep, call stack en basiscase begrijpen.
Waarom wacht faculteit(3) op faculteit(2)?
Verwachte elementen: eerst dieper gaan naar kleinere invoer, daarna terugrekenen; bijvoorbeeld 3 faculteit(2), dan 2 faculteit(1), enzovoort. Laat verschillende formuleringen toe.
Veelgemaakte fout: geen stop
```python
def fout(n):
return fout(n - 1)
```
Deze functie heeft geen basiscase. Daardoor blijft Python nieuwe aanroepen maken en stopt het programma niet vanzelf.
Gebruik dit om het belang van een stopvoorwaarde te laten landen, niet om foutmeldingen technisch uit te diepen.
Veelgemaakte fout: probleem wordt niet kleiner
```python
def fout(n):
if n == 0:
return 0
else:
return fout(n)
```
Er is wel een basiscase, maar de recursieve stap komt daar nooit dichter bij.
Benadruk het verschil tussen 'er is een basiscase' en 'de code bereikt de basiscase ook echt'.
Recursie of lus?
Een `for`- of `while`-lus herhaalt met één functieaanroep
Recursie herhaalt via nieuwe functieaanroepen
Beide kunnen soms hetzelfde probleem oplossen
Recursie past goed bij problemen die natuurlijk in kleinere deelproblemen uiteenvallen
Houd het contrast functioneel, niet ideologisch: recursie is niet altijd beter.
Hetzelfde idee met een lus
```python
def faculteit_lus(n):
uitkomst = 1
for i in range(1, n + 1):
uitkomst *= i
return uitkomst
```
Deze versie gebruikt geen recursie, maar berekent hetzelfde resultaat.
Laat zien dat leerlingen al een alternatief kennen. Zo begrijpen ze recursie als ontwerpkeuze.
Wanneer is recursie handig?
Als een probleem direct uit kleinere versies van zichzelf bestaat
Als je een boomstructuur of geneste structuur verwerkt
Als de oplossing kort en logisch te formuleren is
Noem eventueel kort mappenstructuren of geneste lijsten als herkenbare voorbeelden, zonder nieuwe code uit te werken.
Zo herken je goede recursie
Een recursieve functie is meestal goed opgebouwd als drie dingen kloppen:
er is een duidelijke basiscase
de invoer wordt in de recursieve stap kleiner
elke aanroep komt aantoonbaar dichter bij stoppen
Dit is de samenvattende ontwerpchecklist van de les.
Welke fout heeft wel een basiscase, maar bereikt die niet?
return fout(n - 1)
if n == 0: return 0
return fout(n)
uitkomst *= i
Verwijst naar slides 12–13. De misvatting is dat alleen de aanwezigheid van een basiscase genoeg zou zijn.
Wanneer kies jij eerder voor recursie dan voor een lus?
Bij deelproblemen
Bij boomstructuren
Bij korte logica
Bijna nooit
Deze slide heeft geen instructies
Maak de checklist compleet
Goede recursie herken je zo: er is een duidelijke basiscase, de invoer wordt in de recursieve stap kleiner en elke aanroep komt dichter bij stoppen.
Gebaseerd op de samenvattende ontwerpchecklist van slide 17.
Wat neem jij mee uit deze les over recursie?
Vrije reflectie zonder goed of fout. Laat leerlingen benoemen wat inhoudelijk is blijven hangen, bijvoorbeeld basiscase, call stack of verschil met lussen.
Welk voorbeeld hielp jou het meest begrijpen?
Vrije reflectie. Mogelijke antwoorden: het aftelvoorbeeld, de uitgewerkte faculteit, de vergelijking met een lus, of de checklist met drie voorwaarden.
Welk deel van recursie vond je nog lastig?
Vrije reflectie. Gebruik antwoorden om volgende les extra aandacht te geven aan bijvoorbeeld call stack, returnwaarden of het herkennen van een goede basiscase.
Begrippenlijst
recursie - techniek waarbij een functie zichzelf aanroept
basiscase - situatie waarin de functie direct stopt en een resultaat geeft
recursieve stap - deel van de functie waarin zij zichzelf opnieuw aanroept
functieaanroep - het uitvoeren van een functie met een bepaalde invoer
call stack - stapel waarin Python actieve functieaanroepen bewaart
returnwaarde - waarde die een functie teruggeeft
faculteit - product van alle positieve gehele getallen tot en met een getal
Deze slide heeft geen instructies