Wat is recursie?

Recursie klinkt als een goocheltruc: een functie die zichzelf aanroept. Toch is het idee simpel: als je een groot probleem kunt terugbrengen tot een iets kleiner probleem van dezelfde soort, hoef je alleen het allerkleinste geval zelf op te lossen.

Het idee

De faculteit van 5 is 5 × 4 × 3 × 2 × 1. Maar je kunt ook zeggen: de faculteit van 5 is 5 × (de faculteit van 4). En die is 4 × (de faculteit van 3). Zo ga je door tot de faculteit van 1, en die weet je: 1. Een recursieve functie doet precies dat:

def faculteit(n):
    if n <= 1:
        return 1
    return n * faculteit(n - 1)

De eerste regel na def is het basisgeval: hier stopt het. De laatste regel is de recursieve stap: hetzelfde probleem, één kleiner.

De twee vragen die je altijd stelt

Ten eerste: wanneer stop ik? Zonder basisgeval roept de functie zichzelf eindeloos aan; Python stopt dan met een fout ("maximum recursion depth") en Progio legt uit wat er gebeurde. Ten tweede: wordt het probleem echt kleiner? faculteit(n - 1) gaat richting het basisgeval; faculteit(n) niet. Fibonacci heeft twee basisgevallen (0 en 1) en twee aanroepen: fibonacci(n - 1) + fibonacci(n - 2).

Wanneer recursie handig is

Bij problemen die uit zichzelf bestaan: mappen met mappen erin, een boomstructuur, een figuur die uit kleinere kopieën van zichzelf bestaat (een fractal), en veel zoek- en sorteeralgoritmen. Een lus kan vaak hetzelfde, en is soms sneller; recursie is vaak korter en leesbaarder. Op planeet Progio schrijf je faculteit, som, macht en Fibonacci recursief, met verborgen tests op de basisgevallen (n = 0 vergeten is de klassieke fout).

Efficiëntie

De eenvoudige recursieve Fibonacci berekent dezelfde waarden heel vaak opnieuw: fibonacci(30) doet al meer dan een miljoen aanroepen. Dat is een mooie brug naar efficiëntie: soms is het idee goed en de uitvoering traag, en dan helpt onthouden wat je al hebt uitgerekend. Zie ook functie.