(Unter-)Programme sind rekursiv, wenn sie sich selbst direkt oder indirekt aufrufen. Eine Rekursion läuft, bis sie durch einen Rekursionsanker, eine Abbruchbedingung für eine Rekursion endet. Man unterscheidet zwischen linearen und nicht linearen Rekursionen.
Eine Funktion ist linear rekursiv, wenn nur ein rekursiver Aufruf erfolgt. Für die Fakultätsfunktion könnte das so aussehen:
fakul 0 = 1
fakul n = n(fakul n-1)
Der Computer würde bei Aufruf fakul 3 im ersten Schritt alle Aufrufe auf den Stack legen:
1. fakul 3 = 3 *
2. ( 2 *
4. ( 1 *
5. ( 1 ) ) )
und nach erreichen des Rekursionsankers fakul 0 = 1 alle auf dem Stack abgelegten Zahlen aufmultiplizieren:
5. ( 1 ) ) )
6. ( 1 *
7. ( 2 *
8. 3 *
9. 6 =
Die Rekursion wird also einmal hin und zurück durchlaufen.
fakul 0 a = a
fakul n a = fakul (n-1) (a*n)
Die Variable a läuft bei der Rekursion mit und summiert das Endergebnis auf, so dass beim erreichen des Rekursionsankers das Endergebnis bereits feststeht (Akkumulatortechnik). Diese Variante braucht kaum Speicher, das der Stack nicht mit den rekursiven Aufrufen gefüllt wird.
Eine rekursive Funktion ist nicht-linear rekursiv, wenn die Ausführung zu mehr als einem rekursiven Aufruf führt.
Ein Beispiel für eine nicht-lineare Rekursion ist die Fibonaccifunktion in dieser Form:
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n-1) + fibo (n-2)
Bei der Ausführung spaltet sich die Auswertung der rekursiven Aufrufe logisch in einen Baum:
Endrekursive Algorithmen können entrekursiviert werden. Dazu überführt man den Algorithmus in eine Schleife.
Lineare Algorithmen müssen erst mittels Akkumulatortechnik in eine endrekursive Form überführt werden, um sie entrekursivieren zu können. Nicht-lineare Rekursionen können nicht einfach durch Anwendung eines Schemas entrekursivieren.