Svansrekursion

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Svansrekursion är inom datavetenskap rekursion där sista operationen i en funktion är ett rekursivt anrop. En sådan rekursion kan lätt omvandlas till en iteration, och kan på så sätt drastiskt minska utrymmet i anropsstacken som behöver användas. Svansrekursion används ofta i funktionella programmeringsspråk, exempelvis Scheme.

Beskrivning

När en funktion anropas i ett program måste datorn komma ihåg var den var innan den börjar utföra funktionen, vilket den gör genom att spara en returadress på en stack, så om rekursionen blir djup kommer många returadresser att sparas. Om det rekursiva anropet (då funktionen anropar sig själv) är det sista funktionen utför kan anropet ersättas med ett hopp, då ingen returadress behöver sparas på stacken. Programmet kommer då att återanvända till den ursprungliga anroparen direkt när rekursionen är klar. Att konvertera ett funktionsanrop till ett hopp kallas ibland svansanropsoptimering.

Implementationsmetoder

Svansrekursion är viktigt framförallt för funktionella programmeringsspråk, exempelvis ska Scheme, enligt sin språkdefinition, använda sig av svansrekursion när det är möjligt. Många Scheme-kompilatorer använder C som mellanspråk, så man måste implementera svansrekursion i C. Detta åstadkoms oftast genom att alla funktioner anropas genom en speciell funktion, och när en funktion vill anropa en annan funktion returnerar den istället adressen till funktionen som den vill anropa.