Rekursive Funktionen: Das Rec-Schlüsselwort

Das rec Schlüsselwort wird zusammen mit dem let Schlüsselwort verwendet, um eine rekursive Funktion zu definieren.

Syntax

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

Bemerkungen

Rekursive Funktionen – Funktionen, die sich selbst aufrufen – werden explizit in der F#-Sprache mit dem rec Schlüsselwort identifiziert. Das rec Schlüsselwort stellt den Namen der let Bindung im Textkörper zur Verfügung.

Das folgende Beispiel zeigt eine rekursive Funktion, die die ^{Fibonacci-Zahl} mithilfe der mathematischen Definition berechnet.

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

Hinweis

In der Praxis ist Code wie das vorherige Beispiel nicht ideal, da er unnötig Werte neu kompiliert, die bereits berechnet wurden. Dies liegt daran, dass es nicht rekursiv ist, was weiter in diesem Artikel erläutert wird.

Methoden sind implizit rekursiv innerhalb des Typs, in dem sie definiert sind, was bedeutet, dass das Schlüsselwort nicht hinzugefügt rec werden muss. Beispiel:

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

let Bindungen innerhalb von Klassen sind jedoch nicht implizit rekursiv. Für alle let-gebundenen Funktionen ist das rec Schlüsselwort erforderlich.

Schwanz rekursion

Bei einigen rekursiven Funktionen ist es notwendig, eine "reine" Definition in eine zu umgestalten, die rekursiv ist. Dadurch werden unnötige Neukompilierungen verhindert. Beispielsweise kann der vorherige Fibonacci-Zahlengenerator wie folgt neu geschrieben werden:

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

Das Generieren einer Fibonacci-Zahl ist ein hervorragendes Beispiel für einen "naiven" Algorithmus, der mathematisch rein, aber ineffizient in der Praxis ist. Während dies eine kompliziertere Implementierung ist, machen mehrere Aspekte sie in F# effizient, während sie weiterhin rekursiv definiert sind:

• Eine rekursive innere Funktion namens loop, die ein idiomatisches F#-Muster ist.
• Zwei Akkumulatorparameter, die gesammelte Werte an rekursive Aufrufe übergeben.
• Eine Überprüfung des Werts, n um einen bestimmten Akkumulator zurückzugeben.

Wenn dieses Beispiel iterativ mit einer Schleife geschrieben wurde, würde der Code mit zwei verschiedenen Werten, die Zahlen sammeln, ähnlich aussehen, bis eine bestimmte Bedingung erfüllt wurde.

Der Grund, warum dies tail-rekursiv ist, liegt daran, dass der rekursive Aufruf keine Werte im Aufrufstapel speichern muss. Alle berechneten Zwischenwerte werden über Eingaben an die innere Funktion angesammelt. Dadurch kann der F#-Compiler auch den Code so schnell optimieren, wie wenn Sie etwas wie eine while Schleife geschrieben haben.

Es ist üblich, F#-Code zu schreiben, der etwas rekursiv mit einer inneren und äußeren Funktion verarbeitet, wie das vorherige Beispiel zeigt. Die innere Funktion verwendet Tail-Rekursion, während die äußere Funktion eine bessere Schnittstelle für Aufrufer aufweist.

Ab F# 8.0 können Sie das TailCall Attribut verwenden, um explizit die Absicht anzugeben, eine tail-rekursive Funktion für den Compiler zu definieren. Der Compiler warnt Sie dann, wenn Ihre Funktion rekursive Aufrufe ohne Tail vor sich führt. Sie können das Attribut für Methoden und Funktionen auf Modulebene verwenden.
Beispiel: Verwenden Sie sie in der ersten fib Definition:

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

würde Compilerwarnungen über die beiden nicht-tail rekursiven Aufrufe auslösen.

Sich gegenseitig rekursive Funktionen

Manchmal sind Funktionen sich gegenseitig rekursiv, was bedeutet, dass Aufrufe einen Kreis bilden, wobei eine Funktion eine andere aufruft, die wiederum die erste Aufrufe mit einer beliebigen Anzahl von Aufrufen dazwischen aufruft. Sie müssen solche Funktionen in einer let Bindung zusammen definieren, indem Sie das and Schlüsselwort verwenden, um sie miteinander zu verknüpfen.

Das folgende Beispiel zeigt zwei sich gegenseitig rekursive Funktionen.

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

Rekursive Werte

Sie können auch einen let-gebundenen Wert definieren, der rekursiv sein soll. Dies geschieht manchmal für die Protokollierung. Mit F# 5 und der nameof Funktion können Sie dies tun:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Siehe auch

• Funktionen