Rekursief

Rekursief, ook rekursie genoemd, verwijst naar een proces of definitie die naar zichzelf terugverwijst of op zichzelf voortbouwt. Het begrip komt veel voor in wiskunde, informatica en taalkunde en verwijst naar een regel of methode die zichzelf herhaaldelijk toepast. De term is afgeleid van het Latijnse recursus of het Franse recursif, waarin terugkeren of opnieuw optreden centraal staat.

In wiskunde en logica wordt een rekursive definitie opgebouwd uit twee onderdelen: een basisgeval dat rechtstreeks kan worden toegepast, en een recursieve stap die naar een eenvoudiger of eerder geval verwijst. Een rekursieve structuur, zoals een reeks of een verzameling, wordt zo opgebouwd door herhaalde toepassing van deze stap totdat het basisgeval wordt bereikt.

In informatica verwijst rekursie naar een procedure, functie of algoritme die zichzelf aanroept om een probleem op te lossen. Een essentieel kenmerk is de aanwezigheid van een basisgeval waardoor de recursie stopt. Zonder basisgeval kan een recursief proces eindeloos doorgaan en leidt het tot een stackoverflow. Veel recursieve algoritmen kunnen ook iteratief worden uitgevoerd; sommige talen optimaliseren tail-recursion om geheugen te besparen.

Voorbeelden zijn onder meer de berekening van faculteit (faculteit(n) = n × faculteit(n−1) met faculteit(0) = 1) en de Fibonacci-reeks (fib(n) = fib(n−1) + fib(n−2) met fib(0) en fib(1) als basisgevallen). Rekursie wordt ook toegepast in recursieve datastructuren zoals lijsten en bomen, en in linguïstiek bij het beschrijven van geneste zinsstructuren.