Rekursion

Rekursion er en metode, hvor man definerer noget ved at henvise til sig selv. I matematik betyder det, at et nyt led i en følge, en funktion eller en mængde afhænger af tidligere trin. På den måde kan komplekse strukturer bygges op ud fra en enkel start.

 

Et simpelt eksempel er en rekursivt defineret følge:

 

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

 

Startpunktet er \( \large a_{0} = 1 \). Hvert nyt led findes ved at gange det forrige med 2. Dermed bliver de første værdier

 

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

 

 

Rekursiv og eksplicit form

En rekursiv formel beskriver et led ud fra tidligere led. Ofte kan man også finde en eksplicit formel, hvor hvert led kan beregnes direkte uden at kende de forrige. For eksemplet ovenfor gælder

 

$$ \large a_{n} = 2^n $$

 

Rekursive definitioner er gode til at vise en struktur, mens eksplicitte formler er hurtige til beregning. Begge tilgange er nyttige, og de to hænger tæt sammen.

 

Følger

Rekursion bruges til at definere mange kendte følger. F.eks. Fibonacci-følgen, hvor hvert led er summen af de to foregående.

 

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

 

Funktioner

Et andet eksempel er fakultetsfunktionen. Den kan defineres rekursivt som

 

$$ \large n! = n \cdot (n-1)!, \quad 0! = 1 $$

 

Mængder

Mængder kan også defineres rekursivt. Hvis vi starter med at sige at 3 tilhører mængden, og derefter tilføjer summen af allerede kendte elementer, får vi alle tal der er delelige med 3. Det kan skrives som en rekursiv definition:

 

$$ \large 3 \in M, \quad x \in M \;\Rightarrow\; x + 3 \in M $$

 

Pascals trekant

Et kendt geometrisk eksempel er Pascals trekant. Hvert tal dannes rekursivt som summen af de to tal ovenover. Dette giver en trekantet struktur, der rummer de binomiale koefficienter.

 

$$ \large
\begin{array}{cccccccccccccccccc}
        &       &       &       &       &       &       &       & 1     &       &       &       &       &       &       &       \\
        &       &       &       &       &       &       & 1     &       & 1     &       &       &       &       &       &       \\
        &       &       &       &       &       & 1     &       & 2     &       & 1     &       &       &       &       &       \\
        &       &       &       &       & 1     &       & 3     &       & 3     &       & 1     &       &       &       &       \\
        &       &       &       & 1     &       & 4     &       & 6     &       & 4     &       & 1     &       &       &       \\
        &       &       & 1     &       & 5     &       & 10    &       & 10    &       & 5     &       & 1     &       &       \\
        &       & 1     &       & 6     &       & 15    &       & 20    &       & 15    &       & 6     &       & 1     &       \\
        & 1     &       & 7     &       & 21    &       & 35    &       & 35    &       & 21    &       & 7     &       & 1     \\
  1     &       & 8     &       & 28    &       & 56    &       & 70    &       & 56    &       & 28    &       & 8     &       & 1 \\
\end{array}
$$

 

 

Anvendelse

Rekursion er et grundlæggende redskab i diskret matematik. Det bruges til at beskrive uendelige processer, til at bevise egenskaber ved hjælp af induktion, og til at konstruere algoritmer. Også i geometri spiller rekursion en rolle, for eksempel i opbygningen af fraktaler.

 

 

Sammenhæng med induktion

Når man arbejder med rekursive definitioner, er induktion et naturligt bevisværktøj. Man viser først at en påstand gælder i basis-trinnet, og derefter at den holder fra ét trin til det næste. Dermed kan man bevise egenskaber for hele den uendelige struktur, der er defineret rekursivt.