We hebben gezien dat functies ons in staat stellen om een programma beter te organiseren en delen ervan opnieuw te gebruiken. We hebben ook gezien dat functies kunnen worden gedefinieerd met behulp van andere functies. In deze les zullen we zien dat functies kunnen worden gedefinieerd met behulp van zichzelf! Dit fenomeen wordt recursie genoemd. De legende zegt dat "om recursie te begrijpen, je eerst recursie moet begrijpen".

Voorbeeld

In onze les over loops hebben we een while loop gebruikt om de volgende output te genereren.

5
4
3
2
1
Boemm!

Laten we wat extra print statements gebruiken om ons te helpen het programma te begrijpen. Deze versie leest ook de tijd in vanuit input.

Je kunt Enter input gebruiken om andere input waarden uit te proberen. Probeer eerst 0, kijk wat er gebeurt, en probeer dan 1.

Wanneer de input 5 is, zal het programma eerst een kopie van de countdown-functie aanroepen met n=5. Deze zal 5 printen en countdown(4) aanroepen. Dit gaat zo door totdat countdown(0) wordt aangeroepen, en die print "Boemm!". Vervolgens zal de functie niet langer countdown aanroepen. Wanneer Python stopt met het uitvoeren van de n=0-aanroep van de countdown functie, gaan we terug naar de functie die hem aanriep, namelijk de n=1-aanroep van countdown. Vanaf daar gaan we terug naar de n=2-aanroep, enzovoort.

Om nog even te checken of we het begrijpen zullen we het programma met recursie nog eens stap voor stap bekijken:

Nieuw is, en dat maakt recursieve functies uniek ten opzichte van eerdere functies, dat meerdere versies van dezelfde functie tegelijkertijd in actie zijn. Dat lijkt veel op wat we zagen in Les 10 waar ook de ene functie de andere aanriep, behalve dan dat hier de functie zichzelf aanroept. Merk op dat bij elke stap alleen de op dat moment aanwezige variabelen worden gebruikt en niet de variabelen in de eerder aangeroepen functies. Die variabele staan 'op pauze'.

Het is nu aan jou om een programma te (her)schrijven. Pas de countdown-functie aan zodat het niet aftelt (van boven naar beneden) maar optelt telt (van beneden naar boven).

Programmeeroefening: Boemm na omhoog tellen

Schrijf een recursieve functie countup(n) die 'Boemm!' afdrukt gevolgd door de getallen 1 tot n op gescheiden regels. Hint

Je moet een account aanmaken en inloggen om een vraag te kunnen stellen.

def countdown(n): if n == 0: print('Blastoff!') else: print(n) countdown(n - 1)

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Meer acties... Geschiedenis Reset code to default Help

Pas vervolgens het programma countdown aan zodanig dat in stappen van 2 wordt geteld. De output moet zijn 5, 3, 1, Boemm! We zullen daarvoor het argument in de functie veranderen van n-1 in n-2. Maar moet er nog meer veranderd worden?

Je kunt zien dat het programma niet werkt zoals bedoeld. Het drukt 5, 3, 1 af zoals bedoeld, maar in plaats van te stoppen gaat het verder met -1, -3, -5 en zo gaat het alsmaar door. (Preciezer: na een tijdje raakt de tijd of het geheugen op, omdat elke aanroep bij recursie een beetje extra werkgeheugen vraagt.)

Wanneer we een recursieve functie gebruiken dienen we voorzichtig te zijn dat de aanroepen niet oneindig blijven doorgaan! Pas het countdownBy2-programma hierboven aan zodanig dat het stopt bij 1 (of 2, wanneer n even is) en print dan 'Boemm!'.

Programmeeroefening: Dubbele tijd

Pas dit recursieve programma zo aan dat het aftelt in stappen van 2.

Je moet een account aanmaken en inloggen om een vraag te kunnen stellen.

def countdownBy2(n): if n == 0: print('Boemm!') else: print(n) countdownBy2(n - 2) # verwijder dit commentaar en type hier je code

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Meer acties... Geschiedenis Reset code to default Help

Recursieve functies produceren

Een functie heet recursief wanneer de functie zichzelf aanroept. Maar zo'n programma moet niet steeds zichzelf aanroepen, want dan zal het oneindig lang doorlopen, zoals we boven gezien hebben. Een base case is dat deel van de recursieve functie waarin het zichzelf niet aanroept. In het voorbeeld boven, was de base case n<=0. Een recursieve functie ontwerpen vraagt dat je zorgvuldig een base case kiest en dat bij iedere rij van functie aanroepen tenslotte bij deze base case uitkomt.

In de volgende functie is de base case voor jou al geschreven en moet jij de rest van de recursieve functie schrijven.

Programmeeroefening: Digital Sum

De digitale som van een getal n is de som van zijn cijfers. Schrijf een recursieve functie digitalSum(n) dat een positief geheel getal n als input heeft en zijn digitale som teruggeeft. Zo geeft code>digitalSum(2019) 12 terug omdat 2+0+1+9=12. Hint #1 Hint #2

Je moet een account aanmaken en inloggen om een vraag te kunnen stellen.

def digitalSum(n): if n < 10: return n else: # recursive case # verwijder dit commentaar en type hier je code

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Meer acties... Geschiedenis Reset code to default Help

Nu zullen we een recursieve functie schrijven dat digitalSum aanroept als een subroutine.

Programmeeroefening: Digital Root

De digital root van een niet-negatief geheel getal  n wordt als volgt berekend. Begin met het optellen van de cijfers van n. De cijfers van het resultaat worden opnieuw gesommeerd, en dit proces wordt herhaald tot er maar één cijfer overblijft. Zo is bijvoorbeeld de digital root van 2019 gelijk aan 3 want 2+0+1+9=12 en 1+2=3. Schrijf een recursieve functie digitalRoot(n) die de digital root van n terug geeft.
Neem aan dat een correct werkende versie van digitalSum beschikbaar is voor je programma.

Je moet een account aanmaken en inloggen om een vraag te kunnen stellen.

# verwijder dit commentaar en type hier je code

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Meer acties... Geschiedenis Help

Oefeningen

Oefening met Kort Antwoord: GGD

Wat is de output van het volgende recursieve programma?

def ggd(a, b):
  if b == 0: return a
  return ggd(b, a % b)
print(ggd(20, 12))

Jouw antwoord (voer een getal in):

Correct! Dit opmerkelijk korte programma berekent de grootste gemene deler van twee getallen. Dit staat bekend als het Euclidische algoritme , een van de oudst bekende algoritmes.

Programmeeroefening: Hagelstenen

De hagelsteen-rijdie begint met een positief getal n wordt door de volgende twee eenvoudige regels voortgezet. Als n even is, dan is het volgende getal in de rij n/2. Als n oneven is, dan is het volgende getal in de rij 3*n+1. Wanneer we dit proces herhalen dan zetten we de hagelsteen-rij voort. Schrijf een recursieve functie hagelsteen(n) die de hagelsteen-rij oplevert, te beginnen met n. Stop zodra de rij het getal 1 bereikt (anders zouden we in een oneindige loop terecht komen (1, 4, 2, 1, 4, 2, ...)
Wanneer we bijvoorbeeld n=5 invoeren, dan moet je programma de volgende rij produceren:

5
16
8
4
2
1

Je moet een account aanmaken en inloggen om een vraag te kunnen stellen.

# verwijder dit commentaar en type hier je code

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Meer acties... Geschiedenis Help

Wiskundigen nemen aan dat iedere hagelsteen rij 1 zal bereiken, onafhankelijk van de n waarmee we starten. Maar tot nu toe heeft niemand nog het bewijs kunnen leveren.

Recursie is ook verwant aan fractals — plaatjes die steeds meerdere kleiner kopieën van zichzelf bevatten. De banner aan de kop dan deze webpagina is er een voorbeeld van. De volgende oefening brengt een eenvoudig zich herhalend patroon voort waarbij recursie gebruikt wordt.

Volgorde-oefening: Fractal lijn

Zet de regels in de juiste volgorde zodat het resultaat een programma wordt dat als resultaat een zich herhalend ontwerp heeft. Zo geeft voor n=3 het programma de volgende output.

-
--
-
---
-
--
-

• ruler(n - 1)
• if n == 1:
• print(n * '-')
• ruler(n - 1)
• print('-')
• else:
• def ruler(n):

Gefeliciteerd! Je bent klaar om naar de volgende les te gaan.