engl.: recursion

Eine Definition oder Deklaration nennt man rekursiv, wenn der definierte Begriff bzw. das deklarierte Programmelement im definierenden Teil verwendet wird.

Eine Deklaration P heißt direkt rekursiv, wenn der definierte Ausdruck, bzw. Prozedurrumpf, eine Anwendung von P enthält.

Eine Menge von Deklarationen heißen verschränkt rekursiv oder indirekt rekursiv (engl. mutually recursive), wenn die Deklarationen gegenseitig voneinander abhängen.

Eine Deklaration heißt rekursiv, wenn sie direkt rekursiv ist oder Element einer Menge verschränkt rekursiver Deklarationen ist.

• Rekursive Definitionen finden sich in vielen Bereichen der Informatik und Mathematik, aber auch in anderen Wissenschaften und der nichtwissenschaftlichen Sprachwelt.
• Wir werden hauptsächlich rekursive Funktions- und Datentypdeklarationen betrachten (in der funktionalen Programmierung).
• Diese Definition findet unter anderem vollkommen analoge Anwendung bei den Begriffen der Funktion, der Prozedur, der Klasse und des Datentyps.