Wat is een recursieve oproep?

Bij het programmeren is een recursieve aanroep een opdracht binnen een subroutine of functie die het programma vertelt om dezelfde subroutine opnieuw uit te voeren. De herhaalprestatie kan het directe resultaat van de functie zijn, of een tweede functie kan worden geactiveerd die op zijn beurt terugverwijst naar de eerste functie. Een recursieve aanroep heeft enkele overeenkomsten met de gevreesde oneindige lus, maar de subroutine heeft altijd een voorwaardelijke instructie die het programma vertelt wanneer het moet stoppen met het herhalen van de recursie.

Het concept van recursie wordt misschien het best geïllustreerd door het gebruik van een voorbeeld. Stel dat een dakdekker nieuwe gordelroos op een huis aanbrengt. Om te beginnen moet hij een bundel gordelroos naar het dak dragen. Nadat hij de eerste bundel op zijn plaats heeft genageld, moet hij de ladder af klimmen, een andere bundel ophalen en op zijn plaats spijkeren. Het proces gaat verder als een reeks "ga, haal, keer terug" totdat de laatste grind is aangebracht. Op dat moment is de dakdekker vrij om door te gaan naar de volgende baan of naar huis te gaan.

Hoewel het voorbeeld een vereenvoudiging is, bevat het alle elementen van een recursieve aanroep. Er is een startpunt, de dakdekker moet ophalen wat hij nodig heeft, terugkeren naar het begin en, wanneer aan de laatste voorwaarde is voldaan, stoppen. Dit is eigenlijk wat het programma doet; het begint, implementeert een actie, keert terug naar zichzelf en eindigt wanneer de eindvoorwaarde zich voordoet.

De eindvoorwaarde wordt het basisgeval genoemd. Het is essentieel voor alle recursieve oproepen; zonder dit zou de functie zich blijven herhalen. In het beste geval leidt dit tot een ontlasting van de geheugenbronnen van het systeem. Normaal gesproken zal de overbelasting het programma op een gegeven moment laten crashen, maar tegen de tijd dat het probleem wordt ontdekt, kan er aanzienlijke schade worden aangericht.

Ervaren programmeurs herkennen misschien de gelijkenis tussen een recursieve aanroep en een "for" - of "while" -lus. Als het doel bijvoorbeeld is om de totale voorraadtelling van alle voorraad met onderdeelnummers groter dan 999 te vinden, vertelt een "for" -lus het programma om alle in aanmerking komende instanties te vinden en een "while" -lus vertelt het programma om de lus uit te voeren alleen zolang de vermelde voorwaarde geldig is. Men zou kunnen zeggen dat een recursieve aanroep enkele van de kenmerken van deze lussen combineert met een "if-then-else" -instructie; als deze voorwaarde waar is, doe dit dan, of doe iets anders als de voorwaarde onwaar is. Recursie zorgt meestal echter voor een meer compacte code en zorgt ervoor dat het probleem kan worden doorgegeven aan de functie dichter bij het punt waar het nodig is.