blog placeholder

Wanneer men spreekt van recursie dan spreekt van van het optreden van een conctructie als onderdeel van zichzelf. In de wiskunde en in de informatica worden recursieve constructies veel gebruikt. In de taalkunde wat minder. Dit artikel is gericht op recursie binnen de informatica en de wiskunde. Een voorbeeld van een recursief acroniem is PHP. PHP staat voor PHP Hypertext Preprocessor, waarin de afkorting PHP weer dezelfde betekenis heeft en GNU, GNU is Not Unix.

Recursie komt zoals u net heeft gelezen in de wiskunde en in de informatica veel voor. Zo kunnen bewerkingen op getallen (numerieke waarden) kunnen worden opgeschreven als samenstellingen van willekeurige grootte, bestaande uit bewerkingen (functies) zoals het optellen, aftrekken, vermenigvulgen en delen. Om die reden worden veel wiskundige formules en computertalen (programmeertalen, scripttalen) met recursieve grammatica’s beschreven. Het gebruik van recursie in de informatica kan een functie verkleinen omdat het constant zichzelf aanroept, en kan een functie zichzelf een onbeperkt aantal malen herhalen. Dit gaat in sommige gevallen ten koste van de snelheid waarmee de bewerking wordt gedaan.

Bij een recursieve gegevensstructuur verwijzen een of meer soorten elementen direct of indirect naar dezelfde soort. Bij bijvoorbeeld een boom speelt recursie zich alleen af op soortniveau, een boom bestaat uit knopen waarvan de takken zelf bomen zijn. Een boom kan echter nooit onderdeel zijn van zijn eigen takken.

Bij het gebruik van recursie in een scripttaal of programmeertaal kunnen wanneer de functie niet juist is geschreven oneindige lussen (endless loops) ontstaan.

Toepassingen

Een toepassing van recursie in een programmeertaal is uiteraard om op een korte manier een hele reeks aan berekeningen te definieren. Veel wiskundige vraagstukken van vandaag worden computers op losgelaten omdat deze tot 100 miljard keer sneller kunnen rekenen dan een wiskundige.

Een andere toepassing van recursie is bijvoorbeeld wanneer er sprake is van een SQL database met een oneindig aantal subcategorieen. Wanneer ETEN bestaat uit FRUIT, GROENTE en VLEES, GROENTE kan bestaan uit WORTEL en BLOEMKOOL l, FRUIT kan bestaan uit APPEL en PEER, en APPEL kan bestaan uit ROOD en GROEN dan kan een recursieve functie nagaan wanneer er geen volgende subcategorie meer bestaat.

Nadelen

Recursie lijkt een uiterst geschikte manier om berekeingen op een elegente manier in een functie te schrijven, een nadeel is dat recursie kan zorgen voor veel belasting van de machine waarop het programma draait. Om bijvoorbeeld 1000! (1000 faculteit) uit te rekenen zijn heel erg veel berekeningen nodig. Ook is een for-loop bijzonder effecient vergeleken met een functie die constant zichzelf aanroept.