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:
recursie de meest natuurlijke manier is om de oplossing te implementeren; en
het recursieve proces gegarandeerd niet te diep gaat.