Rekurzív függvények: a rec kulcsszó

A rec rendszer a let kulcsszóval együtt használ egy rekurzív függvényt.

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

Megjegyzések

A rekurzív függvények – magukat nevező függvények – kifejezetten az F# nyelvben vannak azonosítva a rec kulcsszóval. A rec kulcsszó elérhetővé teszi a kötés nevét a let törzsében.

Az alábbi példa egy rekurzív függvényt mutat be, amely az n-edik Fibonacci-számot matematikai definícióval számítja ki.

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

Feljegyzés

A gyakorlatban az előző mintához hasonló kód nem ideális, mert szükségtelenül újrakomponálja a már kiszámított értékeket. Ennek az az oka, hogy nem a farok rekurzív, amelyet ebben a cikkben részletesebben ismertetünk.

A metódusok implicit módon rekurzívak a definiált típuson belül, ami azt jelenti, hogy nincs szükség a rec kulcsszó hozzáadására. Példa:

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

let az osztályokon belüli kötések azonban nem implicit módon rekurzívak. Minden letkötött függvényhez szükség van a kulcsszóra rec .

Farok rekurziója

Egyes rekurzív függvények esetében újra kell dolgozni egy "tiszta" definíciót egy olyanra, amely a tail rekurzív. Ez megakadályozza a szükségtelen újraszámításokat. Az előző Fibonacci számgenerátor például a következőképpen írható át:

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

A Fibonacci-szám létrehozása nagyszerű példa egy olyan "naiv" algoritmusra, amely matematikailag tiszta, de a gyakorlatban nem hatékony. Bár ez egy bonyolultabb implementáció, több szempont is hatékonyabbá teszi az F#-ban, miközben továbbra is rekurzívan definiálva marad:

• Egy rekurzív belső függvény, loopamely egy idiomatikus F# minta.
• Két akkumulátorparaméter, amelyek a halmozott értékeket adják át a rekurzív hívásoknak.
• Egy adott akkumulátor visszaadásának értékének n ellenőrzése.

Ha ez a példa iteratív módon lett megírva egy hurokkal, a kód két különböző értékhez hasonlóan fog kinézni, amelyek számokat halmoznak fel, amíg egy adott feltétel teljesül.

Ennek oka a tail-rekurzív, mert a rekurzív hívásnak nem kell értékeket mentenie a hívásveremen. A kiszámítandó köztes értékek a belső függvény bemeneteivel halmozódnak fel. Ez azt is lehetővé teszi, hogy az F#-fordító ugyanolyan gyorsan optimalizálja a kódot, mintha hurkot while írt volna.

Gyakori, hogy olyan F#-kódot írunk, amely rekurzív módon feldolgoz valamit egy belső és külső függvénnyel, ahogy az előző példa is mutatja. A belső függvény a farok rekurzióját használja, míg a külső függvény jobb felületet biztosít a hívók számára.

Az F# 8.0-tól kezdődően az TailCall attribútum használatával explicit módon megadhatja a tail-rekurzív függvény fordítóhoz való definiálásának szándékát. A fordító ezután figyelmezteti, ha a függvény nem tail rekurzív hívásokat indít. Az attribútum metódusokon és modulszintű függvényeken használható.
Használja például az első fib definícióban:

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

a két nem tail rekurzív hívásra vonatkozó fordítói figyelmeztetéseket váltana ki.

Kölcsönösen rekurzív függvények

Néha a függvények kölcsönösen rekurzívak, ami azt jelenti, hogy a hívások kört alkotnak, ahol az egyik függvény meghív egy másikat, amely viszont az elsőt hívja, tetszőleges számú hívás között. Ezeket a függvényeket egyetlen let kötésben kell definiálnia, a and kulcsszóval összekapcsolva őket.

Az alábbi példa két kölcsönösen rekurzív függvényt mutat be.

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)

Rekurzív értékek

Definiálhat -bound értéket is let, hogy rekurzív legyen. Ez néha a naplózáshoz szükséges. Az F# 5 és a nameof függvény segítségével a következőt teheti:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Lásd még

• Functions