tailrekursjon

Tailrekursjon er en form for rekursjon der den rekursive kallet er den siste operasjonen funksjonen utfører. Dette gjør det mulig for visse språkmiljøer å bruke tail-call optimization (TCO), slik at den nåværende stack-rammen kan erstattes av den neste. Resultatet er at minnebruken ikke nødvendigvis vokser med antall rekursjonsnivåer, og rekursive løsninger kan oppføre seg som iterative.

Forskjellen mellom tailrekursjon og generel rekursjon ligger i hvorvidt resultatet av senere operasjoner avhenger av returverdien fra den rekursive samtalen. I en tailrekursjon er den rekursive kallet i tail-posisjon og direkte returnert. For å oppnå tailrekursjon kan man introdusere en akkumulator som bærer med seg midlertidige resultater gjennom rekursjonen.

Eksempel: beregning av fakultaet. En ikke-tail rekursiv implementasjon er ofte definert som faktorial(n) = n * faktorial(n-1) med operasjonen etter rekursjonen. En tailrekursiv variant bruker en akkumulator:

def faktorial_tail(n, acc=1):

if n == 0:

return acc

return faktorial_tail(n-1, acc*n)

I språk som støtter TCO, som Scheme eller visse kompilatorbaserte språk, vil faktorial_tail kunne kjøre med konstant ekstra minne. I språk uten garantert tail-call-optimering, som Python og mange JavaScript-motorer, kan minnebruken fortsatt vokse med antall rekursjonsnivåer.

Tailrekursjon er spesielt utbredt i funksjonelle språk, men kan være et nyttig verktøy i imperativprogrammering også, enten ved å konvertere rekursive løsninger til løkker eller ved å bruke akkumulatorer for å oppnå bedre plassbruk og ytelse.