Rekursion in

Über Rekursion

Die Fähigkeit, etwas durch sich selbst zu definieren, nennt man Rekursion. In F# begegnet dir Rekursion am häufigsten in rekursiven Funktionen, also Funktionen, die sich selbst aufrufen.

Eine rekursive Funktion braucht mindestens einen Basisfall und mindestens einen Rekursionsfall. Ein Basisfall gibt einen Wert zurück, ohne die Funktion erneut aufzurufen. Ein Rekursionsfall ruft die Funktion erneut auf und verändert die Eingabe so, dass sie irgendwann zum Basisfall passt.

Rekursive Funktionen werden wie normale Funktionen definiert, aber mit dem rec-Modifizierer. Ohne diesen Modifizierer kann eine Funktion sich nicht selbst aufrufen, und jeder Versuch, es doch zu tun, führt zu einem Kompilierungsfehler. Man muss sich also ausdrücklich für Rekursion entscheiden.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

Listen werden oft rekursiv verarbeitet. Hier siehst du zum Beispiel, wie du mit Rekursion die Länge einer Liste berechnest:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

Viele der eingebauten Funktionen sind rekursiv definiert.

Ein mögliches Problem bei rekursiven Funktionen ist, dass jeder (rekursive) Funktionsaufruf Speicher auf dem Stack belegt und ihn dadurch wachsen lässt. Da der Stack nur begrenzt Speicher hat, können Funktionen mit vielen rekursiven Aufrufen eine StackOverflowException auslösen. Wie viele rekursive Aufrufe dieses Verhalten auslösen, hängt von mehreren Faktoren ab, etwa dem verfügbaren Speicher auf dem Stack und davon, wie viele Daten jeder Funktionsaufruf auf dem Stack belegt.

Der beste Weg zu verhindern, dass rekursive Funktionen den Stack überlaufen, ist, sie als endrekursive Funktionen zu schreiben. Wenn eine Funktion endrekursiv ist, kann der Compiler die Ausgabe so optimieren, dass bei jedem rekursiven Funktionsaufruf kein zusätzlicher Speicher auf dem Stack belegt wird. Die eine Regel für endrekursive Funktionen lautet: Das Ergebnis eines rekursiven Funktionsaufrufs muss direkt von der Funktion zurückgegeben werden, es darf keinen zusätzlichen Code geben, der das Ergebnis des rekursiven Aufrufs weiterverarbeitet. Am häufigsten machst du das mit einer Hilfsfunktion, die zusätzlich ein Akkumulator-Argument entgegennimmt, das bei jedem rekursiven Aufruf aktualisiert und am Ende der Rekursion zurückgegeben wird. Diese Seite erklärt sehr ausführlich, wie der Compiler endrekursive Funktionen verarbeitet.

Hier ist eine endrekursive Version der Funktion zur Längenberechnung einer Liste:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

Es ist durchaus üblich, die rekursive Hilfsfunktion als verschachtelte Funktion zu definieren. Dadurch bleibt die rekursive Natur der Funktion vor dem Aufrufer verborgen:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F# unterstützt rekursive Typen über diskriminierte Union-Typen. Bei einem rekursiven diskriminierten Union-Typ beziehen sich einer oder mehrere seiner Fälle in ihren Daten auf den Typ selbst. Wie rekursive Funktionen brauchen auch rekursive Typen einen Basisfall. Anders als rekursive Funktionen verwenden rekursive Typen nicht das Schlüsselwort rec.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

Hier ist eine (nicht endrekursive) Funktion, die mit dem obigen rekursiven Typ arbeitet:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1