Recursie

Het Droste-effect.

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

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

Recursie in de informatica

Deze recursie op soortniveau komt ook in de wiskunde en in de informatica veel voor. Bewerkingen op getallen kunnen bijvoorbeeld worden opgeschreven als willekeurig grote samenstellingen van getallen en bewerkingen zoals optellen, aftrekken, vermenigvuldigen en delen. Veel wiskundige formalismen en computertalen worden daarom met recursieve grammatica's beschreven.

Een andere vorm van recursie op soortniveau is de recursieve gegevensstructuur: deze bevat een of meer soorten elementen die direct of indirect naar elementen van dezelfde soort verwijzen.

Een voorbeeld waarbij de recursie zich alleen op soortniveau afspeelt is de boom: die bestaat uit knopen waarvan de takken zelf bomen zijn, maar een boom kan geen onderdeel zijn van zijn eigen takken.

Daarnaast wordt vaak gebruikgemaakt van werkelijk recursieve datastructuren. Daarvan is bijvoorbeeld sprake als een gerichte graaf wordt gedefinieerd als een verzameling knopen met voor iedere knoop zijn lijst opvolgerknopen: in een graaf kan een knoop direct of indirect zijn eigen opvolger zijn.

Naast gegevensrecursie wordt er vaak gebruikgemaakt van recursie in berekeningen, door deze te definiëren in termen van een recursieve functie: een functie die zichzelf aanroept. In de rekenkunde is dit een heel gangbaar en oud idee; een voorbeeld is het algoritme van Euclides voor het bepalen van de grootste gemene deler van twee gehele getallen.

Voor de beschrijving van bewerkingen op recursieve gegevensstructuren worden meestal recursieve functies gebruikt.

In het gegeven voorbeeld kunnen we bijvoorbeeld maar de directe ondergeschikten van een werknemer ook in de indirecte ondergeschikten geïnteresseerd zijn. De direct ondergeschikten van Peter zijn in één stap te bepalen: het zijn degenen die de waarde "2" (het werknemer_id van Peter) als baas_id hebben (Jan en Roel). Om ook alle ondergeschikten van Peter te vinden, moet hetzelfde proces herhaald worden. Eerst om de ondergeschikten van Jan en Roel te vinden. Voor Jan zijn dat Gert en Harry. Roel heeft geen ondergeschikten. De volgende stap is het opzoeken van de ondergeschikten van Gert en Harry, enzovoort, enzovoort, totdat er geen ondergeschikten meer worden gevonden. Dit "aflopen van een relatie tot alles is gevonden" komt in de praktijk erg vaak voor. Er is dan ook een wiskundige term voor: de relatie "indirecte ondergeschikte" is de transitieve afsluiting van de relatie "directe ondergeschikte".

Het opzoeken van alle ondergeschikten van iemand, kan het best worden gedaan met een recursieve functie, want het proces is elke keer identiek, namelijk: "zoek de id's van alle werknemers met nummer n als baas", waarbij de uitkomst de invoer is van de volgende aanroep van de functie. Het is niet meteen duidelijk hoe vaak de functie herhaald moet worden. Het is wel duidelijk wanneer de functie "klaar" is, namelijk als de nieuw gevonden ondergeschikten zelf geen ondergeschikten meer hebben.

Het is natuurlijk essentieel dat er een moment komt waarop de functie zichzelf niet meer aanroept, anders gaat het proces oneindig door. In het bovenstaande voorbeeld roept de functie zichzelf niet aan als er geen nieuwe ondergeschikten zijn gevonden. Er kunnen ook randvoorwaarden worden geformuleerd, zoals een maximum aan het aantal malen dat een functie zichzelf mag aanroepen.

Een vergelijkbare boomstructuur wordt gevormd door de directory's en bestanden op een computer. Elke directory kan (naast bestanden) zelf ook weer een directory bevatten. Om alle bestanden in een directory en alle onderliggende directory's te vinden, is een recursief proces nodig.

Maar als daarbij ook symbolische links of shortcuts worden gevolgd, is er niet altijd sprake meer van een boom: er kunnen cykels bestaan. Om in zo'n geval te voorkomen dat het proces oneidig lang doorgaat kan bijvoorbeeld tijdens het aflopen worden gecontroleerd of een bereikt element niet al eens eerder is bereikt,

Fractals worden gemaakt door een recursieve functie: op een complex getal wordt een berekening losgelaten. De uitkomst is een nieuw complex getal, dat de invoer vormt voor de volgende aanroep van dezelfde functie. De computergegenereerde plaatjes ontstaan door de complexe getallen op een assenstelsel uit te zetten en de kleur van elk punt te laten bepalen door de einduitkomst na een van tevoren vastgesteld aantal aanroepen.

Andere toepassingen in de informatica die gebruikmaken van recursie zijn o.a. sorteer-algoritmen en de Fourieranalyse.

Nadelen

Vaak is recursie een natuurlijke en elegante manier om functies of procedures te definiëren. In een daadwerkelijke implementatie moet men er echter voorzichtig mee zijn. Hoewel recursie soms snel en efficiënt werkt (zoals bij het sorteeralgoritme Quicksort), is het ook vaak veel trager dan niet-recursieve implementaties. Om bijvoorbeeld 100! (honderd faculteit) recursief uit te rekenen zijn maar liefst honderd functieaanroepen nodig, die ieder een aantal klokcycli nodig hebben, en ook moet elke keer een aantal registers op de stack geplaatst worden. Een eenvoudige for-loop werkt dan sneller en kost minder geheugen.

Recursie in de wiskunde

Ook in de wiskunde wordt gebruikgemaakt van recursieve functies. 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 <math>\mathbb{N}</math> (1 is een element van <math>\mathbb{N}</math>; als x een element van <math>\mathbb{N}</math> is, dan is x+1 ook een element van <math>\mathbb{N}</math>).

Recursieve acroniemen

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

Vormen van recursie

1. Als een functie in een programma eindigt met een aanroep van zichzelf, spreekt men van staartrecursie.
2. Als twee functies elkaar aanroepen, is sprake van wederzijdse recursie.

Zie ook

• Matroesjka-popjes
• Zelfreferentie
• Recursietheorie

Bronnen, noten en/of referenties

Referenties