rekursjon – programmering – Store norske leksikon

Rekursiv programmering er en programmeringsteknikk der en funksjon benytter kall på seg selv for å utføre arbeidet. Hvert påfølgende kall vil som regel løse en stadig mindre (og enklere) del av problemet. Rekursjon kan gi elegante løsninger i programkoden, og benyttes mye innen datastrukturer og matematiske problemer. Det vil imidlertid alltid være mulig å løse de samme problemene uten rekursjon, men programkoden kan bli mer omfattende og komplisert.

Faktaboks

Uttale: rekursjˈon
Etymologi: til rekurrens

Et typisk bruksområde for rekursjon er binærsøk der man søker etter en verdi i en sortert liste. Funksjonen vil først sjekke om midterste verdi i lista er lik tallet det søkes etter. Er den ikke det, utføres den samme funksjonen på øvre eller nedre halvdel av lista avhengig av om tallet i midten av lista var høyere eller lavere enn tallet det søkes etter. Slik fortsetter funksjonen med å halvere søkemengden inntil tallet er funnet eller lista kun inneholder ett element.

Eksempel

For å beregne faktultet (altså 4! = 4 × 3 × 2 × 1 = 24) kan man benytte rekursjon. Hvert funksjonskall i beregningen forsøker da løse et enklere problem, som er å beregne fakultet av en verdi som er lavere. I PHP kan en slik funksjon se slik ut:

$\texttt{function fakultet(\$n) \{}\\ \quad \texttt{if(\$n > 1) \{}\\ \qquad \texttt{ return \$n * fakultet(\$n-1);}\\ \quad \texttt{\}} \\ \quad \texttt{else \{}\\ \qquad \texttt{ return 1;}\\ \quad \texttt{\}} \\ \texttt{\}}$

Les mer i Store norske leksikon

programmering

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

Du må være logget inn for å kommentere.

Fagansvarlig for Programmeringsspråk

Tom Heine Nätt

Førstelektor, Høgskolen i Østfold