Recursie (informatica)

Recursie in informatica en computertechniek is een methode waar de oplossing van een probleem afhangt van oplossingen van kleinere identieke problemen, in tegenstelling tot iteratie.

Deze benadering kan toegepast worden op veel soorten problemen en recursie is een basis van de informatietechnologie. Recursie komt in de wiskunde en in de informatica veel voor. Bewerkingen op getallen kunnen bijvoorbeeld worden geschreven 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.

Gegevensverwerking

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 mappen en bestanden op een computer. Elke map kan (naast bestanden) zelf ook weer een map bevatten. Om alle bestanden in een map en alle onderliggende mappen te vinden, is een recursief proces nodig.

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 oneindig 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. Voor elke recursieve functieaanroep is een aantal klokcycli nodig en ook moet elke keer een aantal registers op de call stack geplaatst worden, met de kans dat er niet genoeg geheugen meer beschikbaar is. Een eenvoudige for-loop werkt dan sneller en kost minder geheugen. Veel compilers kunnen recursie echter herkennen en zodanig vertalen dat het in het uitvoerbare programma niet meer voorkomt. Compilers voor functionele programmeertalen als Lisp en Haskell, bijvoorbeeld, vormen staartrecursieve functies vaak automatisch om tot equivalente niet-recursieve functies.

Vormen van recursie

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