Rekursive Funktionen sind Funktionen, die sich während ihrer Ausführung selbst aufrufen. Dabei kann sich die Funktion sogar mehrmals selbst oder zwei Funktionen sich gegenseitig aufrufen.

Damit sie das nicht endlos tun, muss jede rekursive Funktion eine Bedingung formulieren, in der sie sich nicht weiter selbst aufruft.

Jede rekursive Funktion besitzt demnach einen Basisfall bzw. eine Abbruchbedingung, bei der keine weiteren rekursiven Aufrufe mehr geschehen. Trifft diese Abbruchbedingung nicht zu, geschieht der rekursive Aufruf. Der rekursive Aufruf darf dabei nicht mit den gleichen Argumenten geschehen, die die Funktion selbst erhält, da sonst die Abbruchbedingung nie erreicht werden kann, wodurch die Berechnung nie beendet wird. Die Idee ist also, dass das Ergebnis Schritt für Schritt berechnet wird und jeder rekursive Aufruf einen „kleineren“ Parameter weitergibt, als er selbst bekommen hat.

Verdeutlicht an einem Beispiel:

Die Fakultät Fakultät einer natürlichen Zahl n (geschrieben n!) ist das Produkt von n mit allen natürlichen Zahlen zwischen 1 und n. Beispielsweise ist

5! = 5 * 4 * 3 * 2 * 1 = 120

Diese Funktion soll beispielhaft rekursiv berechnet werden. Als Basisfall gilt, dass 1! = 1 ist.

function Factorial(_X)
    -- Basisfall: Wenn _X = 1 ist, ist das Ergebnis 1
    if _X == 1 then
        return 1
    end
 
    -- In jedem anderen Fall ist das Ergebnis das Produkt zwischen _X und der Fakultät der
    -- nächstkleineren Zahl
    return _X * Factorial(_X - 1)
end

Diese Funktion erfüllt die zwei Bedingungen, die Rekursion braucht, um funktionieren zu können:

1. Es gibt eine Abbruchbedingung, bei der kein rekursiver Aufruf stattfindet
2. Der rekursive Aufruf gibt als Argument eine kleinere Zahl (_X - 1) weiter, als der Funktionsaufruf selbst bekommen hat. So wird sichergestellt, dass die Abbruchbedingung immer erreicht wird (vorausgesetzt, die eingegebene Zahl war positiv)

Zur Veranschaulichung können wir den Funktionsaufruf Factorial(4) „aufrollen“:

Factorial(4)                   <- _X ist hier größer als 1, also rekursiver Aufruf:
  4 * Factorial(3)             <- _X ist hier größer als 1, also rekursiver Aufruf; Factorial(3) ist noch unbekannt
    4 * 3 * Factorial(2)       <- _X ist hier größer als 1, also rekursiver Aufruf; Factorial(2) ist noch unbekannt
      4 * 3 * 2 * Factorial(1) <- _X ist gleich 1, also kann eine sichere Antwort, 1, gegeben werden
      4 * 3 * 2 * 1            <- jetzt können die zuvor unbekannten Ergebnisse oben berechnet werden
    4 * 3 * 2                  <- an der Stelle ist bekannt: Factorial(2) = 2
  4 * 6                        <- an der Stelle ist bekannt: Factorial(3) = 6
24                             <- an der Stelle ist bekannt: Factorial(4) = 24, das Ergebnis ist fertig

(+ Beispiel Fibonacci, Fakultät)