Rekursjon

Rekursjon er (periodisk) gjentakelse, det vil si at noe gjentar seg eller vender tilbake.

Rekursjon i matematikk og informatikk

Rekursjon, eller rekursiv funksjon, er i matematikk og informatikk en måte å definere en funksjon på, der funksjonen selv blir anvendt i sin egen definisjon.

Et enkelt eksempel er fakultet i matematikken, som kan defineres rekursivt som her:

$n!={\begin{cases}1&{\mbox{if }}n\leq 1,\\(n-1)!\times n&{\mbox{if }}n>1.\end{cases}}$

Et eksempel fra informatikk er en klassebeskrivelse av Person:

Person
  navn: Tekst
  barn: Person [0..*]

Denne beskriver at en person kan foruten et tekstlig navn ha null til mange (*) barn som hver av dem er en person som igjen har navn og kanskje barn.

Rekursjon i språkvitenskap

Innen lingvistikken har naturlige språk i tillegg til å bruke slike grammatiske kategorier den viktige egenskapen at de organiserer elementer i rekursive strukturer. En substantivfrase kan inneholde en annen substantivfrase, og en bisetning kan inneholde en annen bisetning. Substantivfrasen kongen av Danmarks sønns favorittsjokolade er et eksempel på dette. Rekursjon var kjent i lingvistikken tidligere (for eksempel gjennom Jespersen), men det var først etter publiseringen av Noam Chomskys bok Syntactic structures i 1957 at man forsto rekkevidden av dette aspektet ved naturlige språk.

Se også

• Droste-effekten eller rekursivt bilde
• Rekursivt akronym
• Rekurrens, gjentakelse, særlig brukt i geologi om fossiler som forekommer i flere lag
• Selvreferanse