engl.: tail recursive

Vereinfachend betrachten wir hier nur Funktionsdeklarationen, bei denen die Fallunterscheidung „außen“ und die rekursiven Aufrufe in den Zweigen der Fallunterscheidung stehen.

• Eine rekursive Funktionsdeklaration heißt linear rekursiv, wenn in jedem Zweig der Fallunterscheidung höchstens eine rekursive Anwendung erfolgt.
• Eine rekursive Funktionsdeklaration heißt repetitiv (rekursiv), wenn sie linear rekursiv ist und die rekursiven Anwendungen in den Zweigen der Fallunterscheidung an äußerster Stelle stehen.
• Eine rekursive Funktionsdeklaration für f heißt geschachtelt rekursiv, wenn sie Teilausdrücke der Form f(…f(…)…) enthält.
• Eine rekursive Funktionsdeklaration für f heißt kaskadenartig rekursiv, wenn sie Teilausdrücke der Form h(…f(…)…f(…)…) enthält.