Eine Operation oder Menge von Operationen ist rekursiv, wenn sie auf ihr eigenes Resultat wieder angewandt wird, und zwar im Prinzip beliebig oft so lange, bis eine passende Abbruchbedingung erfüllt ist. (Rekursion bedeutet wörtlich “Zurücklaufen”.)
Ein rekursive Operation hat folgende allgemeine Form:
| Op: | a | = | f (a) |
|---|
Hier wird die Funktion f auf ein Element a (bzw. von der Kategorie a) angewandt, und das Resultat ist wieder (ein Element der Kategorie) a.
Ein Beispiel aus der Syntax ist die Konstituenz eines endozentrischen Syntagmas, z.B.:
| Op: | Nom | = | Adj + Nom |
|---|
Hier kann das Nom rechts des Gleichheitszeichens seinerseits aus Adj + Nom bestehen, und so weiter im Prinzip beliebig oft.
Eine rekursive Menge von Operationen hat folgende allgemeine Form:
| Opi: | a | = | f (b) |
|---|---|---|---|
| Opj: | . | . | . |
| Opk: | b | = | g (a) |
In Opi resultiert a aus der Anwendung von f auf b, aber b ist seinerseits das Resultat von Opk, wo g auf a angewandt wird. Wird nun diese Menge von Operationen rekursiv angewandt, so besagt dies, daß das in Opi auftretende b aus Opk resultieren und folglich sein eigenes Resultat, nämlich a, bereits als Operanden enthalten kann.
Ein Beispiel aus der Syntax ist die Komplementsatzbildung, die durch folgende Konstituentenstrukturregeln beschrieben werden kann:
| Op1: | S | = | NS + VS |
|---|---|---|---|
| Op2: | NS | = | S |
Gemäß Op1 besteht ein Satz aus Nominalsyntagma und Verbalsyntagma. Gemäß Op2 besteht das Nominalsyntagma seinerseits aus einem Satz (in diesem Falle einem Subjektsatz).
Wenn diese Operationen in einen funktionierenden rekursiven Algorithmus, in diesem Falle zur Erzeugung syntaktischer Konstruktionen, inkorporiert werden sollen, dann müssen sie mit einer Abbruchbedingung bzw. einer Alternative zur Expansion von Nom (im ersten Beispiel) und von NS (im zweiten Beispiel) versehen werden; denn andernfalls geriete erstens der Algorithmus in eine Endlosschleife, und zweitens würden alle Nominalien bzw. alle Nominalsyntagmen diese komplexe Struktur haben, was ja in natürlicher Sprache nicht der Fall ist.
Rekursivität ist eine fundamentale Eigenschaft formaler Sprachen. Sie ist auch in natürlichen Sprachen wichtig. In diesen wird freilich schon nach wenigen Stufen der Schachtelung die resultierende Struktur komplexer, als sie in natürlicher Rede je vorkommen würde. Zudem ist strittig, ob Rekursion für natürliche menschliche Sprachen notwendig ist.