Inhalt

Rekursive Definitionen

Eine rekursive Definition besteht aus zwei Schritten und einer weiteren Eigenschaft:

1. Definition des ersten Elements.
2. Definition einer Regel zur Erzeugung eines neuen, nächsten Elements.
3. Die erzeugte Menge besitzt nur Elemente die aus 1. und 2. in endlich vielen Schritten erzeugt werden können.

Beispiele

Definition der Menge I von Listen aus Einsen

$nil \in I$

$\forall i \in I$

ist

$1 \mid i$

auch ein Element von I (Mit

$\mid$

ist hier die Konkatenation gemeint)

Rekursive Funktionsdefinition

$S:I\rightarrow N$

liefert die Länge einer Liste aus Einsen.BR

$S\left(nil\right)=0$

BR

$S \left(1\mid l\right)=1+S\left(l\right)$

Strukturelle Rekursivität

Eine rekursive Definition ist strukturell rekursiv wenn gilt:

• Jedes Element von I kann nur mit einer der beiden Regeln erzeugt werden
• Regel 2 konstruiert nur "echt grössere" Elemente von I, d.h. Regel zwei greift nur auf echte Teilobjekte des erzeugten Objekts zu.

Zu einer strukturell rekursiv definierten Funktion kann man eine strukturell rekursiv definiterte Funktion definieren. Eine solche Funktion heisst totale Funktion. Die Beispiele oben sind strukturell rekrusiv.

KategorieInformatik KategorieTheoretischeInformatik