Rekursive definitioner

En rekursiv definition er en måde at beskrive et matematisk objekt på ved at henvise til sig selv. For at en sådan definition skal give mening, skal der altid indgå to dele:

 

• Basis: det eller de første trin, som sætter processen i gang.
• Rekursivt skridt: en regel, som forklarer hvordan man danner nye elementer ud fra tidligere.

 

 

Funktioner

Et klassisk eksempel er fakultetsfunktionen. Her er basis og rekursivt skridt:

 

$$ \large 0! = 1 $$

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

 

Basis angiver værdien af \( \large 0! \). Derefter beskriver det rekursive skridt, hvordan \( \large n! \) beregnes ud fra \( \large (n-1)! \). På den måde kan man finde alle værdier af fakultet trin for trin.

 

Eksempel

Vi kan beregne de første værdier:

 

$$ \large 0! = 1 \quad \text{(basis)} $$

$$ \large 1! = 1 \cdot 0! = 1 $$

$$ \large 2! = 2 \cdot 1! = 2 $$

$$ \large 3! = 3 \cdot 2! = 6 $$

$$ \large 4! = 4 \cdot 3! = 24 $$

 

Hvert skridt bygger direkte på det forrige, indtil vi når frem til den ønskede værdi.

 

 

Funktioner på strenge

Rekursive definitioner kan også bruges på symbolstrenge. Et eksempel er funktionen \( \large L(s) \), der angiver længden af en streng \( \large s \):

 

$$ \large L(\varepsilon) = 0 $$

$$ \large L(x \cdot s) = 1 + L(s) $$

 

Her betyder \( \large \varepsilon \) den tomme streng, og \( \large x \cdot s \) er en streng, der består af et første tegn \( \large x \) efterfulgt af resten \( \large s \). Basis siger at den tomme streng har længde 0, og det rekursive skridt siger, at man får længden af en længere streng ved at tælle 1 oven i længden af resten.

 

 

Opsummering

En rekursiv definition er altid bygget af et klart startpunkt og en regel for at komme videre. Denne opdeling i basis og rekursivt skridt gør det muligt at opbygge komplekse strukturer på en præcis og systematisk måde. Uanset om man arbejder med tal, strenge eller geometriske figurer, er rekursive definitioner et fundamentalt værktøj.