Rekursion er et fundamentalt begreb inden for datalogi og matematik. En definition eller beskrivelse er rekursiv, hvis det beskrevne eller definerede begreb forklares vha. begrebet selv. En beregning af en funktion er rekursiv, hvis funktionen selv anvendes undervejs i beregningen.

Faktaboks

Etymologi

af lat. recursio, af re- og currere 'løbe'

Et eksempel på en rekursiv definition er definitionen af Fibonaccitallene. Disse er tallene 0, 1, 1, 2, 3, 5, 8, 13, 21, ... , hvor de to første tal er 0 og 1, og hvert af de følgende tal er summen af de to foregående. Når talrækken defineres formelt, defineres \(F(0) = 0\) og \(F(1) = 1\). Alle efterfølgende tal defineres nu ud fra de foregående tal ved formlen \(F(n) = F(n−1)+F(n−2)\). Den generelle definition udnytter, at hvis man allerede har defineret de to første Fibonaccital, kan resten af tallene afledes. For at finde \(F(4)\) udregner man \[F(4) = F(3)+F(2)\]\[ = (F(2)+F(1))+(F(1)+F(0))\]\[ = ((F(1)+F(0))+F(1))+(F(1)+F(0))\]\[ = ((1+0)+1)+(1+0) = 3.\] Som det fremgår af eksemplet, er det også nærliggende at beskrive beregningsprocedurer rekursivt, og grundidéen er den samme: Det ønskede resultat udtrykkes som en funktion af delresultater, der hver for sig beregnes ved anvendelsen af den samme procedure. Et eksempel herpå er en metode til at afgøre, om et givet tal \(a\) forekommer i en liste \(L\) af tal. Enten er \(a\) lig det første tal i \(L\), eller også kan svaret findes ved at bruge samme metode på den liste, der fås ved at fjerne det første tal fra \(L\). Med \(a = 13\) og \(L = (1, 27, 14, 12, 3)\) beregnes svaret på spørgsmålet "Er \(a\) med i \(L\)?" altså ved at kombinere svaret på "Er \(a = 1\)?" med svaret på "Er \(a\) med i \((27, 14, 12, 3)\)?", hvor det sidste spørgsmål kan besvares med den samme metode. Processen stopper ved, at \(a\) findes som det første tal i listen, eller ved, at der ikke er flere tal tilbage.

Rekursivitet spiller en fremtrædende rolle i forbindelse med studier af grænserne for beregnelighed. En funktion kaldes beregnelig, hvis dens værdi kan beregnes af en computer. Klassen af funktioner med denne egenskab viser sig at være lig klassen af funktioner, der kan opbygges vha. ganske få fundamentale operationer, blandt hvilke en form for rekursion er en af de vigtigste. Beregnelige funktioner kaldes derfor også for rekursive funktioner.

Kommentarer

Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.

Du skal være logget ind for at kommentere.

eller registrer dig