Rekursive Definitionen

Eine rekursive Definition ist eine Möglichkeit, ein mathematisches Objekt zu beschreiben, indem man auf sich selbst verweist. Damit eine solche Definition Sinn ergibt, muss sie immer zwei Teile enthalten:

 

• Basis: der oder die ersten Schritte, die den Prozess starten.
• Rekursiver Schritt: eine Regel, die erklärt, wie man neue Elemente aus früheren bildet.

 

 

Funktionen

Ein klassisches Beispiel ist die Fakultätsfunktion. Hier sind Basis und rekursiver Schritt:

 

$$ \large 0! = 1 $$

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

 

Die Basis gibt den Wert von \( \large 0! \) an. Dann beschreibt der rekursive Schritt, wie \( \large n! \) aus \( \large (n-1)! \) berechnet wird. Auf diese Weise können alle Werte der Fakultät Schritt für Schritt gefunden werden.

 

Beispiel

Wir können die ersten Werte berechnen:

 

$$ \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 $$

 

Jeder Schritt baut direkt auf dem vorherigen auf, bis wir den gewünschten Wert erreichen.

 

 

Funktionen auf Zeichenketten

Rekursive Definitionen können auch auf Zeichenketten angewandt werden. Ein Beispiel ist die Funktion \( \large L(s) \), die die Länge einer Zeichenkette \( \large s \) angibt:

 

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

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

 

Hier bedeutet \( \large \varepsilon \) die leere Zeichenkette, und \( \large x \cdot s \) ist eine Zeichenkette, die aus einem ersten Symbol \( \large x \) und dem Rest \( \large s \) besteht. Die Basis besagt, dass die leere Zeichenkette die Länge 0 hat, und der rekursive Schritt besagt, dass man die Länge einer längeren Zeichenkette erhält, indem man 1 zur Länge des Restes addiert.

 

 

Zusammenfassung

Eine rekursive Definition besteht immer aus einem klaren Startpunkt und einer Regel, um weiterzukommen. Diese Aufteilung in Basis und rekursiven Schritt ermöglicht es, komplexe Strukturen präzise und systematisch aufzubauen. Ob man mit Zahlen, Zeichenketten oder geometrischen Figuren arbeitet – rekursive Definitionen sind ein grundlegendes Werkzeug.