Recursie in Python

Recursie in Python

1 / 32
volgende
Slide 1: Slide
newEditorInformaticaVoortgezet speciaal onderwijsLeerroute 4Leerroute 5Leerroute 6

In deze les zitten 32 slides, met interactieve quizzen en tekstslides.

time-iconLesduur is: 45 min
Dit is niet oké

Onderdelen in deze les

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?

A

Een kleiner probleem

B

Een for-lus

C

Een globale variabele

D

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.

zichzelf aan
basiscase
recursieve stap
while-lus
returnwaarde
call stack

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)?

A

Door de for-lus

B

Door de printvolgorde

C

Door de open berekeningen

D

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.

aanroep
call stack
basiscase
while-lus
parameter
uitvoer

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?

A

return fout(n - 1)

B

if n == 0: return 0

C

return fout(n)

D

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?

1

Bij deelproblemen

2

Bij boomstructuren

3

Bij korte logica

4

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.

basiscase
recursieve stap
stoppen
for-lus
printen
optellen

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