Recursieve functies

We hebben reeds gezien dat je een functie vanuit een functie kunt aanroepen. Een zeer "extreme" vorm daarvan zijn recursieve functies.

Een recursieve functie is een functie die zichzelf aanroept, direct of indirect, om een kleiner exemplaar van hetzelfde probleem op te lossen. Recursie is een veelgebruikte techniek in de informatica en programmeren, en het is met name handig voor het oplossen van problemen die kunnen worden opgesplitst in kleinere, vergelijkbare deelproblemen.

Hier is een eenvoudig voorbeeld van een recursieve functie in Python die de faculteit van een getal berekent:

def faculteit(n):

    if n == 0 of n == 1:

        return 1

    else:

        return n * faculteit(n-1)

In dit voorbeeld wordt `faculteit(n)` gedefinieerd in termen van zichzelf door `faculteit(n-1)` aan te roepen. Het basisgeval (`n == 0 of n == 1`) is belangrijk om te voorkomen dat de recursie oneindig doorgaat.

Recursie kan een krachtige en elegante manier zijn om bepaalde problemen op te lossen, maar het is belangrijk om het verstandig te gebruiken, omdat het anders tot stack overflow-fouten kan leiden als het niet goed is geïmplementeerd. Elke recursieve oproep voegt een nieuw frame toe aan de oproepstack, en als de recursie te diep gaat, kan deze de capaciteit van de stack overschrijden.

Hier is nog een voorbeeld van een eenvoudige recursieve functie die het nth Fibonacci-getal berekent:

def fibonacci(n):

    if n <= 1:

        return n

    else:

        return fibonacci(n-1) + fibonacci(n-2)

Ook hier roept de functie zichzelf aan met kleinere exemplaren van hetzelfde probleem totdat het het basisgeval bereikt (`n <= 1`), waar het een specifieke waarde retourneert.