Recursie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Recursie is het optreden van een constructie als onderdeel van zichzelf. Recursieve constructies worden veelvuldig gebruikt in de wiskunde, informatica en logica en in de (generatieve) taalkunde.

Recursie in de taalkunde[bewerken]

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: de grammaticale categorie van de zin is recursief. (Zinnen zelf zijn dat niet.) 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 herhaald kan worden: "je horloge stuk is" kan uitgebreid worden naar "je horloge stuk is omdat het gevallen is waarna er een auto overheen reed die ...". Sommige taalkundigen menen dat recursiviteit het belangrijkste element is van de taal van mensen[1]


Recursie in de wiskunde[bewerken]

Nuvola single chevron right.svg Zie differentievergelijking voor het hoofdartikel over dit onderwerp.

Ook in de wiskunde wordt gebruikgemaakt van recursieve functies (ook differentievergelijkingen of recurrente betrekkingen). Een bekend voorbeeld is de functie waarmee in de wiskunde de faculteit van een getal kan worden berekend.

De randvoorwaarde is:

0! = 1

De recursieve definitie is:

n! = n * (n-1)!   voor een natuurlijk getal n>0

Aan de hand van deze functie kunnen we nu de faculteit van het getal 3 uitrekenen:

3! =
3 * (3-1)! =
3 * 2! =
3 * 2 * (2-1)! =
3 * 2 * 1! =
3 * 2 * 1 * (1 - 1)! =
3 * 2 * 1 * 1 =
6

Andere voorbeelden zijn o.a.

  • de rij van Fibonacci (ƒ(n) = ƒ(n-1) + ƒ(n-2))
  • de definitie van de verzameling van natuurlijke getallen \mathbb{N} (1 is een element van \mathbb{N}; als x een element van \mathbb{N} is, dan is x+1 ook een element van \mathbb{N}).

Recursieve acroniemen[bewerken]

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

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

Zie ook[bewerken]

Bronnen, noten en/of referenties
  1. M.D. Hauser e.a. Science 298, 1569 (2002); The Faculty of Language: What Is It, Who Has It and How Did It Evolve?