Рекурсія у

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

Рекурсивні функції - це функції, які викликають самі себе.

Рекурсивна функція повинна мати щонайменше один базовий випадок і щонайменше один рекурсивний випадок.

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

Дуже часто кожен випадок записують в окремому варіанті визначення функції.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

Рекурсивна функція може мати багато базових випадків і/або багато рекурсивних випадків. Наприклад, послідовність Фібоначчі - це рекурсивна послідовність із двома базовими випадками:

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

Підрахунок кількості входжень заданого значення x у масиві має два рекурсивні випадки:

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Цикли через рекурсію

Через незмінність цикли в Elixir записують інакше, ніж в імперативних мовах. Наприклад, цикли зазвичай мають такий вигляд:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

У функціональній мові змінити i (викликавши i++) неможливо. Тож цикли доводиться реалізовувати через рекурсію.

Аналог циклу for в Elixir мав би такий вигляд:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

На практиці для перебирання елементів масивів та інших перелічуваних структур даних найчастіше використовують модуль Enum. Усередині функції з модуля Enum реалізовано через рекурсію.

Нескінченне виконання

Якщо рекурсивну функцію реалізувати неправильно, вона може так і не повернути результат. Це може бути проблемою, бо щоразу, коли функція викликається, у памʼяті зберігається посилання на те місце, куди віртуальна машина має повернути результат (у стеку викликів). Якщо рекурсивна функція викликає себе нескінченно, памʼять може вичерпатися, і віртуальна машина аварійно завершиться (помилка переповнення стеку). Віртуальна машина Erlang, на якій працює Elixir, спеціально оптимізована для рекурсії та надійності, тож може минути чимало часу, перш ніж помилки нескінченної рекурсії стануть помітними або трапиться аварія.

Цю проблему нескінченного виконання можуть спричиняти:

• Забути реалізувати базовий випадок.
• Не визначити базовий випадок першим варіантом.
• Не змінити належним чином аргумент під час рекурсивного виклику і тому так і не дійти до базового випадку.