Rekursion nenne ich eine Darstellungsart von Algorithmen, in welcher eine Beschreibung einer Operation einen Verweis auf diese Beschreibung enthält.

Rekursionen ohne Abbruchkriterium ergeben unendliche Verschachtelungen. Mani Matter hat das seinem Lied "Bim Coiffeur" besungen.

In dieser Darstellung steht ”|” für ”oder”. ”Ausdruck” wird, wie früher erwähnt, rekursiv generiert. Jeder Ausdruck beginnt mit einem einzelnen Zeichen. Wenn der Ausdruck mehrstellig ist, enthält er das Nichtterminal ”Ausdruck”, das wiederum ”Ausdruck” enthalten kann (Todesco 1992:165).

Informatik-Duden schreibt begriffslos:
Definition eines Verfahrens durch sich selbst. (sic!)

In einer Programm-Procedur wird die Procedur aufgerufen.
Die Procedur muss natürlich ein Haltekriterium enthalten.

Die Programmiersprache Pascal unterscheidet Rekursion und Iteration

Beispiel aus der (Pascal)Programmierung:

procedure P
begin
if .. then
begin
A; P
end
end