Rekursiv

Rekursiv betegner noe som refererer til seg selv eller som løser problemer ved å dele dem i mindre, tilsvarende deloppgaver. I matematikk og logikk brukes rekursive definisjoner og rekursive funksjoner der man følger et basistilfelle og en regel som gjelder for større tilfeller.

I informatikk beskriver rekursjon en metode der en funksjon kaller seg selv for å løse et problem. En basistilfelle stopper rekursjonen, mens det rekursive tilfellet bruker løsningen av en mindre oppgave. Uten tilstrekkelig basistilfelle kan rekursjon bli uendelig eller kreve mye minne, og noen språk tilbyr tailrekursjon som kan optimalisere minnebruken.

Rekursjon forekommer ofte i algoritmer og datastrukturer, spesielt i trær og grafalgoritmer, i divide-and-conquer-løsninger, samt i rekursive definisjoner i teoretiske språk. Det finnes også mutual rekursjon hvor to eller flere funksjoner kaller hverandre.

Enkle eksempler er fakultetsberegning: n! = n × (n−1)!, med 0! = 1, og Fibonacci-tallene beregnet ved summen av de to foregående verdiene. I praksis diskuteres og velges rekursive eller iterative løsninger ut fra ytelse og minnebruk.

Historisk har rekursjon spilt en viktig rolle i matematikk og datavitenskap. I moderne programmering er rekursjon et vanlig verktøy i funksjonelle språk, mens mange imperativspråk tilbyr støtte for tailrekursjon eller alternativ iterasjon.