Recursie
 |
|
Recursie is het opgebouwd zijn van een geheel uit onderdelen van hetzelfde type als het geheel. Recursieve constructies worden veelvuldig gebruikt in de wiskunde, informatica en logica en in de (generatieve) taalkunde.
Inhoud |
[bewerk] Recursie in de taalkunde
In de taalkunde doet recursie zich onder andere voor in de zinsbouw: een zin kan in een andere zin ingebed zijn.
- 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 gereden die ...".
[bewerk] Recursie in de informatica
Een recursieve functie is een functie die zichzelf aanroept. Dat is bijvoorbeeld handig bij het werken met boomstructuren. Een boomstructuur volgt op elk niveau dezelfde regels, dus de bewerking (functie) is voor elk niveau identiek.
Voorbeeld
De hierbij getoonde tabel in een database toont een voorbeeld van een baas-ondergeschikte relatie. Een dergelijke tabel wordt een recursieve tabel genoemd, omdat in dezelfde tabel bij elke werknemer een verwijzing staat naar een andere rij in diezelfde tabel. De tabel verwijst dus naar zichzelf. Dit is een methode om een boomstructuur in een relationele database op te slaan.
Het is in één stap te zien wie de direct ondergeschikten van Peter zijn, namelijk diegenen die de waarde "2" (het werknemer_id van Peter) als baas_id hebben (Jan en Roel). Maar om ook alle (ook de indirect) 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.
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.
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.
[bewerk] 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 veel sneller en kost ook veel minder geheugen.
[bewerk] 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 N. (0 en 1 zijn elementen van N, als x een element van N is, dan is x+1 ook een element van N).
[bewerk] Recursieve acroniemen
Sommige acroniemen zijn recursief gedefinieerd, en dus komt het acroniem terug in de betekenis voor:
[bewerk] Vormen van recursie
- Als een functie in een programma eindigt met een aanroep van zichzelf, spreekt men van staartrecursie.
- Als twee functies elkaar aanroepen, is sprake van wederzijdse recursie.
