Rekurzivní funkce: Klíčové slovo rec

Článek
11/10/2023

Klíčové rec slovo se používá společně s klíčovým slovem let k definování rekurzivní funkce.

Syntaxe

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

Poznámky

Rekurzivní funkce – funkce, které sami volají – jsou explicitně identifikovány v jazyce F# klíčovým slovem rec . Klíčové rec slovo zpřístupňuje název let vazby v textu.

Následující příklad ukazuje rekurzivní funkci, která vypočítá n^fibonacciho číslo pomocí matematické definice.

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

Poznámka:

V praxi není kód podobný předchozímu vzorku ideální, protože zbytečně rekomputuje hodnoty, které už byly vypočítány. Je to proto, že není rekurzivní, což je vysvětleno dále v tomto článku.

Metody jsou implicitně rekurzivní v rámci typu, ve kterém jsou definovány, což znamená, že není nutné přidat rec klíčové slovo. Příklad:

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

let vazby v rámci tříd však nejsou implicitně rekurzivní. Všechny letfunkce vázané na rec vazbu vyžadují klíčové slovo.

Rekurze ocasu

U některých rekurzivních funkcí je nutné refaktorovat "čistou" definici na druhou, která je rekurzivní. Tím se zabrání zbytečným rekomputacím. Například předchozí fibonacciho generátor čísel lze přepsat takto:

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

Generování fibonacciho čísla je skvělým příkladem "naïve" algoritmu, který je matematicky čistý, ale neefektivní v praxi. I když se jedná o složitější implementaci, několik aspektů umožňuje efektivní v jazyce F# i nadále rekurzivně definované:

Rekurzivní vnitřní funkce s názvem loop, která je idiomatickou vzorem jazyka F#.
Dva parametry akumulátoru, které předávají kumulované hodnoty rekurzivním voláním.
Kontrola hodnoty n vrácení konkrétního akumulátoru.

Pokud by byl tento příklad napsán iterativním způsobem s smyčkou, kód by vypadal podobně se dvěma různými hodnotami, které se shromádují čísla, dokud nebude splněna určitá podmínka.

Důvodem, proč je to koncová rekurzivní volání, je, že rekurzivní volání nemusí ukládat žádné hodnoty v zásobníku volání. Všechny zprostředkující hodnoty, které se počítají, se shromáždí vstupy do vnitřní funkce. Kompilátor jazyka F# také umožňuje optimalizovat kód tak rychle, jako kdybyste napsali něco jako smyčku while .

Běžně se píše kód jazyka F#, který rekurzivně zpracovává něco pomocí vnitřní a vnější funkce, jak ukazuje předchozí příklad. Vnitřní funkce používá koncovou rekurzi, zatímco vnější funkce má lepší rozhraní pro volající.

Počínaje jazykem F# 8.0 můžete pomocí TailCall atributu explicitně uvést záměr definovat koncovou rekurzivní funkci kompilátoru. Kompilátor vás pak upozorní, pokud vaše funkce provádí nechvostná rekurzivní volání. Atribut můžete použít u metod a funkcí na úrovni modulu.
Například ho použijete v první fib definici:

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

aktivuje upozornění kompilátoru týkající se dvou nechvostových rekurzivních volání.

Vzájemně rekurzivní funkce

Někdy se funkce vzájemně rekurzivní, což znamená, že volání tvoří kruh, kde jedna funkce volá druhou, která zase volá první, s libovolným počtem volání mezi. Tyto funkce musíte definovat společně v jedné let vazbě pomocí klíčového and slova, které je propojí dohromady.

Následující příklad ukazuje dvě vzájemně rekurzivní funkce.

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)

Rekurzivní hodnoty

Můžete také definovat hodnotu vázanou letna rekurzivní. To se někdy provádí pro protokolování. S jazykem nameof F# 5 a funkcí to můžete udělat takto:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Viz také

Functions

Sdílet prostřednictvím