Рекурсія у

Про концепцію Рекурсія

Здатність чогось визначатися через самого себе називається рекурсією. У F# рекурсія найчастіше зустрічається в рекурсивних функціях, тобто функціях, які викликають самі себе.

Рекурсивна функція повинна мати принаймні один базовий випадок і принаймні один рекурсивний випадок. Базовий випадок повертає значення, не викликаючи функцію знову. Рекурсивний випадок викликає функцію знову, змінюючи вхідні дані так, щоб вони в якийсь момент відповідали базовому випадку.

Рекурсивні функції визначають так само, як звичайні, але з модифікатором rec. Без цього модифікатора функція не зможе викликати саму себе, і будь-яка спроба це зробити призведе до помилки компіляції. Отже, рекурсію потрібно явно увімкнути.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

Масиви часто обробляють за допомогою рекурсії. Наприклад, ось як скористатися рекурсією, щоб обчислити довжину масиву:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

Багато вбудованих функцій визначено рекурсивно.

Одна з можливих проблем рекурсивних функцій полягає в тому, що кожен (рекурсивний) виклик функції спричиняє виділення памʼяті в стеку, через що стек зростає. Оскільки обсяг памʼяті в стеку обмежений, функції з великою кількістю рекурсивних викликів можуть спричинити виняток StackOverflowException. Скільки саме рекурсивних викликів призведе до цього, залежить від багатьох чинників: від доступної памʼяті в стеку та від того, скільки даних займає кожен виклик функції в стеку.

Найкращий спосіб не допустити переповнення стека рекурсивними функціями - писати їх як хвостові рекурсивні функції. Коли функція хвостово-рекурсивна, компілятор може оптимізувати свій вивід так, що кожен рекурсивний виклик функції не додає виділень памʼяті в стеку. Єдине правило для хвостових рекурсивних функцій: результат рекурсивного виклику потрібно повертати з функції безпосередньо, без жодного додаткового коду, який обробляє результат цього виклику. Найпоширеніший спосіб зробити це - створити допоміжну функцію, яка приймає додатковий аргумент-акумулятор, що оновлюється на кожному рекурсивному виклику й повертається, коли рекурсія завершується. Ця сторінка дуже докладно розповідає про те, як компілятор обробляє хвостові рекурсивні функції.

Ось хвостова рекурсивна версія функції для довжини масиву:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

Досить часто рекурсивну допоміжну функцію визначають як вкладену, що приховує рекурсивну природу функції від того, хто її викликає:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F# підтримує рекурсивні типи через дискриміновані обʼєднання. У рекурсивного дискримінованого обʼєднання один або кілька випадків посилаються у своїх даних на сам цей тип. Як і рекурсивні функції, рекурсивні типи повинні мати базовий випадок. Але на відміну від рекурсивних функцій, рекурсивні типи не використовують ключове слово rec.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

Ось функція (не хвостова рекурсивна) для роботи з наведеним вище рекурсивним типом:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1