Rekursionsstacken

Rekursionsstacken, ofta kallad call stacken, är en minnesstruktur som används av ett program för att hantera aktiva funktionsanrop. Varje gång en funktion anropas skapas en ny aktiveringspost (stackram) och placeras på toppen av rekursionsstacken. När funktionen återvänder tas ramens uppgifter bort och kontrollen återgår till anroparen. Stacken är i regel per tråd och hanteras av körmiljön eller operativsystemet.

En stackram innehåller vanligtvis information som returadress, funktionsparametrar, lokala variabler och eventuella sparade register eller temporära värden. Genom att organisera dessa uppgifter i ramar kan programmet snabbt återgå till rätt plats efter varje anrop och isolera varje funktionskörning från andra.

När programmerare skriver rekursion ökar antalet aktiva funktionsanrop med varje djupet överskridande. Om djupet blir för stort kan rekursionsstacken ta slut, vilket leder till en stackoverflow eller liknande fel. Vissa språk och kompilatorer erbjuder optimeringar som kallas tail call optimization (TCO), där ett avslutande funktionsanrop i en funktion kan återanvända den aktuella ramen och därmed begränsa stackanvändningen vid tailrekursion.

Användningen av rekursionsstacken påverkas också av arkitektur och miljö. Vissa system har hårt begränsad stackstorlek, och utvecklare kan behöva justera den eller omvandla rekursion till iteration vid djupare rekursion. Vid felsökning används ofta stacktraces som visar sekvensen av aktiva anrop i störtillståndet. Rekursionsstacken är central för kontrollflöde och minneshantering i många programspråk och körmiljöer.