Funkcje rekurencyjne: rec — Słowo kluczowe

Słowo rec kluczowe jest używane razem ze let słowem kluczowym, aby zdefiniować funkcję rekursywną.

Składnia

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

Uwagi

Funkcje cykliczne — funkcje wywołujące się samodzielnie — są jawnie identyfikowane w języku F# za pomocą słowa kluczowego rec . Słowo rec kluczowe udostępnia nazwę let powiązania w jego treści.

W poniższym przykładzie przedstawiono funkcję rekursywną, która oblicza n^{numer Fibonacciego} przy użyciu definicji matematycznej.

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

Uwaga

W praktyce kod podobny do poprzedniego przykładu nie jest idealny, ponieważ niepotrzebnie ponownie oblicza wartości, które zostały już obliczone. Wynika to z faktu, że nie jest rekursywny, co zostało wyjaśnione w tym artykule.

Metody są niejawnie rekursywne w obrębie zdefiniowanego typu, co oznacza, że nie ma potrzeby dodawania słowa kluczowego rec . Na przykład:

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

let powiązania w klasach nie są jednak niejawnie rekursywne. Wszystkie letfunkcje -bound wymagają słowa kluczowego rec .

Rekursja ogonowa

W przypadku niektórych funkcji cyklicznych należy refaktoryzować bardziej "czystą" definicję do tej, która jest rekursywna. Zapobiega to niepotrzebnym rekomputacji. Na przykład poprzedni generator liczb Fibonacciego można przepisać w następujący sposób:

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

Generowanie liczby Fibonacciego jest doskonałym przykładem algorytmu "naiwnego", który jest matematycznie czysty, ale nieefektywny w praktyce. Chociaż jest to bardziej skomplikowana implementacja, kilka aspektów sprawia, że jest ona wydajna w języku F#, a jednocześnie pozostaje rekursywnie zdefiniowana:

• Rekursywna funkcja wewnętrzna o nazwie loop, która jest idiotycznym wzorcem języka F#.
• Dwa parametry akumulatorowe, które przekazują skumulowane wartości do wywołań cyklicznych.
• Sprawdzanie wartości n w celu zwrócenia określonego akumulatora.

Jeśli ten przykład został napisany iteracyjnie za pomocą pętli, kod będzie wyglądać podobnie do dwóch różnych wartości zbierających liczby do momentu spełnienia określonego warunku.

Powodem, dla którego jest rekursywne jest to, że wywołanie rekursywne nie musi zapisywać żadnych wartości w stosie wywołań. Wszystkie obliczane wartości pośrednie są akumulowane za pośrednictwem danych wejściowych do funkcji wewnętrznej. Dzięki temu kompilator języka F# może zoptymalizować kod tak szybko, jak w przypadku pisania czegoś takiego jak pętla while .

Często pisze się kod języka F#, który cyklicznie przetwarza coś z funkcją wewnętrzną i zewnętrzną, jak pokazano w poprzednim przykładzie. Funkcja wewnętrzna używa rekursji ogonowej, podczas gdy funkcja zewnętrzna ma lepszy interfejs dla wywołań.

Począwszy od języka F# 8.0, możesz użyć atrybutu TailCall , aby jawnie określić intencję definiowania funkcji rekursywnej tail-recursive w kompilatorze. Kompilator wyświetli ostrzeżenie, jeśli funkcja wykonuje wywołania niecykliczne. Możesz użyć atrybutu w metodach i funkcjach na poziomie modułu.
Na przykład użycie go w pierwszej fib definicji:

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

Wyzwalałoby ostrzeżenia kompilatora dotyczące dwóch wywołań cyklicznych innych niż tail.

Funkcje wzajemnie rekursywne

Czasami funkcje są wzajemnie rekursywne, co oznacza, że wywołania tworzą okrąg, gdzie jedna funkcja wywołuje inną, która z kolei wywołuje pierwszą, z dowolną liczbą wywołań między. Takie funkcje należy zdefiniować razem w jednym let powiązaniu, używając słowa kluczowego and , aby połączyć je ze sobą.

W poniższym przykładzie przedstawiono dwie wzajemnie rekursywne funkcje.

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)

Wartości cykliczne

Można również zdefiniować letwartość -bound, która ma być rekursywna. Czasami jest to wykonywane na potrzeby rejestrowania. Za pomocą języka F# 5 i nameof funkcji można to zrobić:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Zobacz też

• Funkcje