Staartrecursie

Uit Wikipedia, de vrije encyclopedie

Een staartrecursie (Engels: tail recursion) is een programmeerconcept in de informatica.

Bij een procedure spreekt men over staartrecursie indien de recursieve oproep de laatste instructie van de procedure is. Bij een normale procedure-aanroep moeten alle lokale variabelen worden opgeslagen zodat de procedure verder kan worden uitgevoerd zodra de aangeroepen procedure eindigt. Als de recursieve aanroep echter de laatste instructie is, is dit niet nodig, omdat de procedure onmiddellijk na het uitvoeren van de aanroep eindigt. Daarom kan een procedure met een staartrecursie eenvoudig worden omgevormd tot een niet-recursieve procedure met een equivalente iteratie.

Sommige compilers optimaliseren een geval van staartrecursie door niet voor iedere recursieve oproep een nieuw stackframe te alloceren, maar de oude opnieuw te gebruiken. Dit leidt tot minder vertraging en minder kans op een stack-overflow.