Recursieve functies: het trefwoord rec

2023-11-10

Het rec trefwoord wordt samen met het let trefwoord gebruikt om een recursieve functie te definiëren.

Syntaxis

// 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
...

Opmerkingen

Recursieve functies - functies die zichzelf aanroepen - worden expliciet geïdentificeerd in de F#-taal met het rec trefwoord. Het rec trefwoord maakt de naam van de binding beschikbaar in de let hoofdtekst.

In het volgende voorbeeld ziet u een recursieve functie waarmee het ne Fibonacci-getal wordt berekend met behulp van de wiskundige definitie.

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

Notitie

In de praktijk is code zoals het vorige voorbeeld niet ideaal, omdat deze waarden die al zijn berekend onnodig opnieuw compileren. Dit komt doordat het niet recursief is, wat verder wordt uitgelegd in dit artikel.

Methoden zijn impliciet recursief binnen het type waarin ze zijn gedefinieerd, wat betekent dat het trefwoord niet hoeft te worden toegevoegd rec . Voorbeeld:

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

let bindingen binnen klassen zijn echter niet impliciet recursief. Voor alle let-afhankelijke functies is het rec trefwoord vereist.

Staartrecursie

Voor sommige recursieve functies is het noodzakelijk om een meer 'pure' definitie te herstructureren op een definitie die recursief is. Dit voorkomt onnodige hercomputaties. De vorige Fibonacci-nummergenerator kan bijvoorbeeld als volgt worden herschreven:

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

Het genereren van een Fibonacci-getal is een goed voorbeeld van een 'naïef' algoritme dat wiskundig puur maar inefficiënt is in de praktijk. Hoewel dit een gecompliceerdere implementatie is, maken verschillende aspecten het efficiënt in F# en blijven recursief gedefinieerd:

Een recursieve binnenfunctie met de naam loop, een idiomatisch F#-patroon.
Twee accumulatorparameters, die samengevoegde waarden doorgeven aan recursieve aanroepen.
Een controle op de waarde van het retourneren van n een specifieke accumulator.

Als dit voorbeeld iteratief met een lus is geschreven, zou de code er ongeveer uitzien als twee verschillende waarden die getallen accumuleren totdat aan een bepaalde voorwaarde is voldaan.

De reden waarom dit tail-recursief is, is omdat de recursieve aanroep geen waarden op de aanroepstack hoeft op te slaan. Alle tussenliggende waarden die worden berekend, worden verzameld via invoer naar de binnenste functie. Hierdoor kan de F#-compiler de code zo snel mogelijk optimaliseren alsof u iets als een while lus hebt geschreven.

Het is gebruikelijk om F#-code te schrijven die recursief iets verwerkt met een interne en buitenste functie, zoals in het vorige voorbeeld wordt weergegeven. De binnenste functie maakt gebruik van tail-recursie, terwijl de buitenste functie een betere interface heeft voor bellers.

Vanaf F# 8.0 kunt u het TailCall kenmerk gebruiken om expliciet aan te geven dat u een tail-recursieve functie wilt definiëren voor de compiler. De compiler waarschuwt u vervolgens als uw functie recursieve aanroepen uitvoert. U kunt het kenmerk gebruiken voor methoden en functies op moduleniveau.
Gebruik deze bijvoorbeeld voor de eerste fib definitie:

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

zou compilerwaarschuwingen activeren over de twee niet-tail recursieve aanroepen.

Wederzijds recursieve functies

Soms zijn functies wederzijds recursief, wat betekent dat aanroepen een cirkel vormen, waarbij de ene functie een andere functie aanroept die op zijn beurt de eerste aanroept, met een willekeurig aantal aanroepen ertussen. U moet dergelijke functies in één let binding definiëren met behulp van het and trefwoord om ze aan elkaar te koppelen.

In het volgende voorbeeld ziet u twee recursieve functies die wederzijds recursief zijn.

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)

Recursieve waarden

U kunt ook een let-gebonden waarde definiëren die recursief moet zijn. Dit wordt soms gedaan voor logboekregistratie. Met F# 5 en de nameof functie kunt u dit doen:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Zie ook

Functies

Delen via