Рекурсивные функции. Ключевое слово rec

Статья
11/10/2023

Ключевое слово rec используется вместе с let ключевое слово для определения рекурсивной функции.

Синтаксис

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

Замечания

Рекурсивные функции - функции, которые вызывают себя- определяются явным образом на языке F# с rec помощью ключевое слово. Ключевое слово rec делает имя привязки доступной let в его тексте.

В следующем примере показана рекурсивная функция, вычисляющая n-е число Fibonacci с помощью математического определения.

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

Примечание.

На практике код, как и предыдущий пример, не является идеальным, так как он ненужно перекомпитирует значения, которые уже вычислены. Это связано с тем, что это не рекурсивный хвост, который объясняется далее в этой статье.

Методы неявно рекурсивны в типе, в который они определены, то есть нет необходимости добавлять rec ключевое слово. Например:

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

let Привязки в классах неявно рекурсивны, однако. Все letфункции с привязкой требуют rec ключевое слово.

Рекурсия хвоста

Для некоторых рекурсивных функций необходимо рефакторинг более чистого определения на тот, который является рекурсивным. Это предотвращает ненужные повторное вычисление. Например, предыдущий генератор чисел Fibonacci можно переписать следующим образом:

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

Создание числа Fibonacci является отличным примером "наивного" алгоритма, который математически чистый, но неэффективный на практике. Хотя это более сложная реализация, некоторые аспекты делают его эффективным в F# при сохранении рекурсивного определения:

Рекурсивная внутренняя функция с именем loop, которая представляет собой идиоматический шаблон F#.
Два параметра аккумулятора, которые передают накопленные значения рекурсивным вызовам.
Проверка по значению n возврата определенного аккумулятора.

Если этот пример был написан итеративно с циклом, код будет выглядеть аналогично двумя различными значениями, накапливающими числа до выполнения определенного условия.

Причина, почему это рекурсивный хвост, заключается в том, что рекурсивный вызов не должен сохранять значения в стеке вызовов. Все промежуточные значения, вычисляемые, накапливаются с помощью входных данных внутренней функции. Это также позволяет компилятору F# оптимизировать код так же быстро, как если бы вы написали что-то подобное while циклу.

Обычно создается код F#, который рекурсивно обрабатывает что-то с внутренней и внешней функцией, как показано в предыдущем примере. Внутренняя функция использует рекурсию хвоста, а внешняя функция имеет лучший интерфейс для вызывающих.

Начиная с F# 8.0, атрибут можно использовать TailCall для явного определения функции рекурсивного хвоста компилятору. Компилятор будет предупреждать вас, если функция выполняет рекурсивные вызовы, отличные от хвоста. Атрибут можно использовать для методов и функций уровня модуля.
Например, используя его в первом fib определении:

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

вызовет предупреждения компилятора о двух рекурсивных вызовах, отличных от хвоста.