Rekursjon

Rekursjon er en metode for å løse et problem ved å dele det inn i mindre, lignende problemer av samme type. En rekursiv løsning består vanligvis av to deler: et base-case som gir et direkte svar uten videre oppdeling, og et rekursivt kall som løser et mindre utgangspunkt ved å bruke samme tilnærming. Når rekursive kall skjer, blir mellomresultater lagret på en kallstack og hentes tilbake når basen er nådd og løsningene bygges opp igjen.

Historisk og teoretisk brukes rekursjon i matematikk til å definere objekter der hvert element er definert i forhold til tidligere elementer, for eksempel faktorial og fibonaccitallene, samt andre rekursive definisjoner. Innen informatikk er rekursjon et vanlig verktøy for å formulere algoritmer og datastrukturer, som hurtigsortering, dybde-først-søk i grafer og trær, og visse typer dynamisk programmering. Viktige begreper inkluderer base-case, rekursivt kall og mutual rekursjon hvor to eller flere funksjoner kaller hverandre.

Ytelse og begrensninger: rekursive løsninger kan være enkle å forstå og implementere, men innebærer ofte overhead fra funksjonskall og risiko for stack overflow ved stor rekursjonsdybde. Tail recursion-optimalisering i enkelte språk kan gjøre rekursjon like effektiv som iterasjon ved at rekursjonen kan omdannes til en iterativ prosess når rekursjonskallet er det siste i funksjonen.

Rekursjon har hatt stor betydning i matematikk og informatikk og fungerer som et fundamentalt verktøy for å undersøke og formulere problemer gjennom oppdeling i enklere delproblemer og rekursive definisjoner.