Rekursive Funktionen: Das rec-Schlüsselwort

Das Schlüsselwort rec wird gemeinsam mit dem Schlüsselwort let 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 in der Sprache F# explizit mit dem Schlüsselwort rec gekennzeichnet. Das Schlüsselwort rec macht den Namen der let-Bindung im zugehörigen Textkörper verfügbar.

Das folgende Beispiel zeigt eine rekursive Funktion, die die n-te Fibonacci-Zahl anhand 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 ein Code wie das vorige Beispiel nicht ideal, da er bereits berechnete Werte unnötigerweise neu berechnet. Das liegt daran, dass er nicht endrekursiv ist, was in diesem Artikel näher erläutert wird.

Methoden sind innerhalb des Typs, in dem sie definiert sind, implizit rekursiv, d. h. das Schlüsselwort rec muss nicht hinzugefügt werden. 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. Alle let-gebundenen Funktionen erfordern das Schlüsselwort rec.

Endrekursion

Für einige rekursive Funktionen muss eine mathematisch „reinere“ Definition in eine endrekursive Definition umgestaltet werden. Dies verhindert unnötige Neuberechnungen. Der vorherige Fibonacci-Zahlengenerator kann zum Beispiel wie folgt umgeschrieben 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

Die Generierung einer Fibonacci-Zahl ist ein gutes Beispiel für einen „naiven“ Algorithmus, der zwar mathematisch rein, aber in der Praxis ineffizient ist. Dies ist zwar eine kompliziertere Implementierung, aber aufgrund verschiedener Aspekte ist sie in F# effizient und bleibt dennoch rekursiv definiert:

• Eine rekursive innere Funktion namens loop, bei der es sich um ein idiomatisches F#-Muster handelt.
• Zwei Akkumulatorparameter, die akkumulierte Werte an rekursive Aufrufe übergeben.
• Eine Überprüfung des Werts von n, um einen bestimmten Akkumulator zurückzugeben.

Wenn dieses Beispiel iterativ mit einer Schleife geschrieben würde, sähe der Code ähnlich aus. Zwei verschiedene Werte akkumulieren Zahlen, bis eine bestimmte Bedingung erfüllt ist.

Dieses Beispiel ist endrekursiv, weil der rekursive Aufruf keine Werte in der Aufrufliste speichern muss. Alle berechneten Zwischenwerte werden über Eingaben in die innere Funktion akkumuliert. Dadurch kann der F#-Compiler den Code so optimieren, dass er genauso schnell ist wie etwa beim Schreiben einer while-Schleife.

Es ist üblich, F#-Code zu schreiben, der eine rekursive Verarbeitung mit einer inneren und äußeren Funktion durchführt, wie das vorherige Beispiel zeigt. Die innere Funktion verwendet die Endrekursion, während die äußere Funktion über eine bessere Schnittstelle für Aufrufer verfügt.

Ab F# 8.0 können Sie das TailCall-Attribut verwenden, um explizit die Absicht anzugeben, eine endrekursive Funktion für den Compiler zu definieren. Der Compiler warnt Sie dann, wenn Ihre Funktion nicht-endrekursive Aufrufe tätigt. Sie können das Attribut für Methoden und Funktionen auf Modulebene verwenden.
Beispiel: Wenn Sie es bei der ersten fib-Definition verwenden:

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

würde es Compilerwarnungen über die beiden nicht-endrekursiven Aufrufe auslösen.

Wechselseitig rekursive Funktionen

Gelegentlich sind Funktionen wechselseitig rekursiv, d. h. die Aufrufe bilden einen Kreis, bei dem eine Funktion eine andere aufruft, die wiederum die erste aufruft. Zwischen dem ersten und dem letzten Aufruf kann eine beliebige Anzahl von Aufrufen liegen. Sie müssen solche Funktionen zusammen in einer let-Bindung definieren und sie durch das Schlüsselwort and miteinander verknüpfen.

Das folgende Beispiel zeigt zwei wechselseitig 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 als rekursiv definieren. Dies geschieht manchmal zur Protokollierung. Dazu können Sie F# 5 und die Funktion nameof verwenden:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Siehe auch

• Funktionen