Рекурсія — це коли функція викликає саму себе. В Elixir, де немає циклів, рекурсія є основним способом обробки колекцій та повторюваних операцій.
Проста рекурсія
Базова рекурсивна функція складається з двох частин: базового випадку та рекурсивного виклику:
# Факторіал
defmodule Math do
def factorial(0), do: 1
def factorial(n) when n > 0 do
n * factorial(n - 1)
end
end
Math.factorial(5)
# 120 (5 * 4 * 3 * 2 * 1)
# Сума списку
defmodule ListHelper do
def sum([]), do: 0
def sum([head | tail]) do
head + sum(tail)
end
end
ListHelper.sum([1, 2, 3, 4, 5])
# 15Проблема простої рекурсії
Проста рекурсія створює стек викликів, що може призвести до переповнення пам'яті:
# Неефективна рекурсія
def factorial(5)
5 * factorial(4)
4 * factorial(3)
3 * factorial(2)
2 * factorial(1)
1 * factorial(0)
1
# Тепер обчислюємо назад:
1 * 1 = 1
2 * 1 = 2
3 * 2 = 6
4 * 6 = 24
5 * 24 = 120
# Для великих чисел це займає багато пам'яті!Хвостова рекурсія
Хвостова рекурсія — це коли рекурсивний виклик є останньою операцією функції. Elixir оптимізує такі виклики:
defmodule Math do
# Хвостова рекурсія з акумулятором
def factorial(n), do: factorial(n, 1)
defp factorial(0, acc), do: acc
defp factorial(n, acc) when n > 0 do
factorial(n - 1, n * acc)
end
end
Math.factorial(5)
# 120
# Хвостова рекурсія для суми списку
defmodule ListHelper do
def sum(list), do: sum(list, 0)
defp sum([], acc), do: acc
defp sum([head | tail], acc) do
sum(tail, acc + head)
end
end
Порада: У хвостовій рекурсії використовується акумулятор (acc) для збереження проміжного результату. Це дозволяє оптимізувати виклики.
Порівняння: проста vs хвостова рекурсія
| Характеристика | Проста рекурсія | Хвостова рекурсія |
|---|---|---|
| Пам'ять | O(n) — стек викликів | O(1) — константна |
| Швидкість | Повільніше | Швидше |
| Читабельність | Часто простіша | Потребує акумулятор |
| Використання | Малі дані | Великі дані |
Практичні приклади
# Довжина списку
defmodule ListOps do
def length(list), do: length(list, 0)
defp length([], acc), do: acc
defp length([_head | tail], acc) do
length(tail, acc + 1)
end
end
# Реверс списку
defmodule ListOps do
def reverse(list), do: reverse(list, [])
defp reverse([], acc), do: acc
defp reverse([head | tail], acc) do
reverse(tail, [head | acc])
end
end
ListOps.reverse([1, 2, 3])
# [3, 2, 1]
# Map для списку
defmodule ListOps do
def map(list, func), do: map(list, func, [])
defp map([], _func, acc), do: reverse(acc)
defp map([head | tail], func, acc) do
map(tail, func, [func.(head) | acc])
end
defp reverse(list), do: reverse(list, [])
defp reverse([], acc), do: acc
defp reverse([h | t], acc), do: reverse(t, [h | acc])
end
ListOps.map([1, 2, 3], &(&1 * 2))
# [2, 4, 6]Коли використовувати рекурсію
- Обробка списків: коли потрібно пройтися по всіх елементах
- Деревоподібні структури: обхід дерев, вкладених даних
- Математичні обчислення: факторіал, Фібоначчі, GCD
- Розділяй і володарюй: швидке сортування, злиття
Увага: Для простих операцій зі списками краще використовувати модуль
Enum замість власної рекурсії. Пишіть рекурсивні функції тільки коли це дійсно потрібно.
Альтернатива: модуль Enum
# Замість рекурсії використовуйте Enum
list = [1, 2, 3, 4, 5]
# Замість власної sum
Enum.sum(list)
# 15
# Замість власної map
Enum.map(list, &(&1 * 2))
# [2, 4, 6, 8, 10]
# Замість власної filter
Enum.filter(list, &(&1 > 3))
# [4, 5]
# Складні операції
list
|> Enum.filter(&(rem(&1, 2) == 0))
|> Enum.map(&(&1 * 3))
|> Enum.reduce(0, &+/2)
# 18Ключові поняття
- Базовий випадок: умова виходу з рекурсії (обов'язкова!)
- Рекурсивний випадок: виклик функції з меншими даними
- Акумулятор: змінна для збереження проміжних результатів
- Хвостовий виклик: рекурсивний виклик як остання операція
- TCO: Tail Call Optimization — оптимізація хвостових викликів
Коментарі
Дописати коментар