Module 7: Recursie
|
Leerdoelen
- Een recursieve functie herkennen en maken
|
Recursie is een speciale techniek die je kunt gebruiken nu je geleerd hebt om functies te maken. Recursie kan bepaalde problemen op een elegante en krachtige manier oplossen.
7.1 Wat is recursie?
Recursie is een techniek waarbij een functie zichzelf aanroept. Een functie roept dus een andere functies aan op zo’n manier dat de uitvoering van de eerste functie nog steeds bezig is wanneer deze functie zelf nogmaals wordt aangeroepen. Bijvoorbeeld, functie a() roept functie b() aan, die dan functie a() weer aanroept.
Dit klinkt misschien vreemd als je het voor het eerst aantreft, maar er is niks op tegen dat een functie andere functies aanroept, en een functie mag iedere functie aanroepen die gedefinieerd is op het moment dat de functie wordt aangeroepen. Omdat een functie gedefinieerd moet zijn voordat hij wordt aangeroepen, kan hij dus zichzelf aanroepen.
“Maar,” hoor ik iemand al protesteren: “als een functie zichzelf aanroept, dan roept hij zichzelf nogmaals aan, en nogmaals, en nogmaals… Betekent dat dan niet dat je een eindeloos proces krijgt, net als bij een eindeloze loop?” Het antwoord is dat er inderdaad het gevaar bestaat dat een recursieve functie, die slordig in elkaar is gestoken, een eindeloze serie aanroepen veroorzaakt. Maar recursieve functies moeten ontworpen worden op een manier dat dat niet gebeurt.
Er zijn veel problemen waarvoor recursie een elegante oplossing biedt. Daarom is het belangrijk dat je je bewust bent van de mogelijkheden van recursie, en dat je weet hoe je het kunt toepassen… en dat je weet wat de beperkingen zijn.
7.2 Recursieve definities
Een voorbeeld van een recursieve definitie is de definitie van de faculteit, die ik al heb geïntroduceerd in twee eerdere hoofdstukken. In die hoofdstukken gaf ik de volgende definitie van de faculteit: de faculteit van een positief geheel getal is dat getal, vermenigvuldigd met alle positieve gehele getallen die kleiner zijn (exclusief nul).
Wiskundigen prefereren een recursieve definitie: De faculteit n! van een positief getal n wordt als volgt berekend: 1!=1, en n!=n∗(n−1)! voor n>1.
Deze definitie is recursief omdat het refereert aan de faculteit van n−1 om de faculteit van n te definiëren. Dit leidt niet tot eindeloze recursie, omdat op enig moment n gelijk zal zijn aan 1, en de faculteit van 1 is apart gedefinieerd.
Je kunt de faculteit als een recursieve functie als volgt implementeren:
Zie hoe deze functie exact de recursieve definitie van de faculteit volgt: als n gelijk is aan 1, retourneert de functie 1, en anders retourneert het n keer de faculteit van n-1. (Merk op dat ik n <= 1 schreef in plaats van n == 1 om te voorkomen dat er problemen ontstaan als de gebruiker de functie aanroept met, bijvoorbeeld, een negatieve n.)
Voor het geval je het problematisch vindt om te begrijpen wat deze functie doet, beschrijf ik hieronder de aanroepen die de functie doet als hij wordt aangeroepen met 5 als argument. Ik laat aanroepen inspringen als een “hoger-niveau aanroep” nog steeds actief is als de aanroep wordt gemaakt. Een “return” die één inspringing dieper gaat dan een “aanroep,” wordt gegeven in die aanroep, en retourneert de gegeven waarde.
Iedere recursieve functie kan ook als een iteratief proces gebouwd worden. Zo nu en dan kom je echter een probleem tegen waarvoor de recursieve oplossing veel eleganter, leesbaarder, en onderhoudbaarder is dan de iteratieve variant. In dat geval moet je overwegen een recursieve oplossing te implementeren.
Je moet alleen recursieve implementaties bouwen als:
