Recursie

Recursie (Latijn: recurrere, 'teruglopen') is het optreden van een opeenvolging van constructies waarvan elk afzonderlijk gebaseerd is op een of meer soortgelijke voorgaande constructies. Doorgaans verschilt de volgende constructie in waarde van de voorgaande en is er een beginpunt. Recursieve constructies komen enerzijds in de taalkunde voor en anderzijds in de wiskunde, informatica, natuurwetenschappen en logica.

Een speciaal geval van recursiviteit is het droste-effect, waarbij een volgende constructie een verkleind beeld is van de voorgaande.

In de taalkunde doet recursie zich onder andere voor in de zinsbouw. De recursie doet zich hier niet voor op het niveau van individuele voorkomens, maar op soortniveau. Zo kunnen zinnen willekeurig diep binnen andere zinnen worden ingebed. Voorbeeld:

Het feit dat je horloge stuk is betekent niet dat je te laat mag komen.

Afgezien van de afwijkende woordvolgorde zijn de ingebedde delen volledige zinnen. Het proces van inbedding is recursief omdat het, in theorie, willekeurig vaak kan worden herhaald : je horloge stuk is kan worden uitgebreid naar je horloge is stuk, omdat het is gevallen, waarna er een auto overheen reed die ... .

Sommige taalkundigen menen dat recursiviteit het belangrijkste element is van de taal van mensen.^[1]

Een voorbeeld is de bijzin. Een vereenvoudigde productieregel kan luiden:

1. Z → ND WD

d.w.z. een zin Z bestaat uit een naamwoordelijk deel ND en een werkwoordelijk deel WD.

2. WD → W ND*

een werkwoordelijk deel bestaat uit een werkwoord W en een of meer naamwoordelijk delen als voorwerp bij het werkwoord.

3. WD → W Z

een werkwoordelijk deel bestaat uit een werkwoord W en een bijzin als voorwerp bij het werkwoord.

Vormt men een zin met regel 1 en 3, dan is er recursie, aangezien in regel 3 weer een zin voorkomt.

Zie Differentievergelijking voor het gebruik van recursiviteit in de wiskunde, Recursie (informatica) voor de informatica en Zelfreferentie voor de logica.

In de wiskunde wordt gebruikgemaakt van recursieve functies, zij worden gegeven door differentievergelijkingen of, synoniem, recurrente betrekkingen. Een voorbeeld is de recursieve definitie van de faculteit (!) van een natuurlijk getal.

De beginvoorwaarde is:

${\displaystyle 1!=1}$

De recursieve definitie is:

${\displaystyle n!=n\cdot (n-1)!}$

Een ander voorbeeld is de rij van Fibonacci:

${\displaystyle f_{n}=f_{n-1}+f_{n-2},\,{\text{voor }}n>1}$

met als startwaarden

${\displaystyle f_{0}=0}$

${\displaystyle f_{1}=1}$

Overeenkomstig deze definities kunnen de faculteit en de rij van Fibonacci in een computerprogramma in een recursieve functie worden geïmplementeerd, de functie roept dan steeds zichzelf aan. Recursie is niet in alle programmeertalen mogelijk.

Recursie komt in de natuur veelvuldig voor^[2]. Enkele voorbeelden:

• condensatie, kristalvorming
• clustering, sneeuwbaleffect
• chemische reacties onder invloed van een katalysator (bv. ontsteking)
• kettingreactie (bv. in een atoombom)
• groei, celdeling
• zelforganisatie (bv. ontwikkeling van het brein)
• fractals in de natuur (bv. varenblad)
• opeenvolging van generaties

In het algemeen leidt recursie in de natuur tot een grotere mate van ordening en/of complexiteit, waardoor de entropie lokaal afneemt (maar macroscopisch toeneemt). Het resultaat van zo'n recursief proces kan emergent zijn als die eigenschappen heeft die niet aanwezig zijn bij voorafgaande generaties. Het recursieve proces kan in principe eindeloos doorgaan, mits de omstandigheden (de randvoorwaarden, bv. voldoende vrije energie) dat toestaan. Het ontstaan van een recursief proces kan ook als een emergent verschijnsel worden opgevat^[3].

Sommige acroniemen zijn recursief gedefinieerd, het acroniem komt in de betekenis terug:

• GNU: GNU's Not Unix
• Wine: Wine Is Not an Emulator
• PHP: PHP: Hypertext Preprocessor
• LAME: Lame Ain't an Mp3 Encoder