Бесплатный курс по Elixir. Зарегистрируйтесь для отслеживания прогресса →

Elixir: Рекурсия

В Эликсир, как и во всех функциональных языках, нет циклов. Их заменяет рекурсия.

Пример 1

Начнем сразу с практики, рассмотрим пример функции, которая вычисляет длину списка:

def len([]), do: 0
def len([_head | tail]) do
  1 + len(tail)
end

len([1,2,3,4,5]) # 5
len([]) # 0

Функция len состоит из двух тел. Первое тело вызывается на пустом списке, и это наше условие выхода из рекурсии. Здесь все просто -- длина пустого списка 0. Второе тело вызывается на непустом списке, и это один шаг (одна итерация) обработки списка.

Здесь мы делаем классическое для функционального программирования разделения списка на голову и хвост:

[_head | tail]

(Переменная _head в дальнейшем не используется, поэтому её имя начинается с подчеркивания). Здесь логика тоже очень простая -- длина списка, это 1 плюс длина хвоста списка.

На каждой итерации список уменьшается на один элемент, пока не становится пустым. А пустой список попадает в первое тело функции, что завершает рекурсию.

Для списка [1, 2, 3, 4, 5] стек вызовов функции будет выглядеть так:

len([1,2,3,4,5])
1 + len([2,3,4,5])
1 + 1 + len([3,4,5])
1 + 1 + 1 + len([4,5])
1 + 1 + 1 + 1 + len([5])
1 + 1 + 1 + 1 + 1 + len([])
1 + 1 + 1 + 1 + 1 + 0

Пример 2

Возьмем пример немного сложнее, реализуем функцию, которая возвращает максимальный элемент в списке.

def list_max([]), do: nil
def list_max([elem]), do: elem
def list_max([head | tail]) do
  max(head, list_max(tail))
end

list_max([1,3,33,42,100500,-10]) # 100500
list_max([1]) # 1
list_max([]) # nil

Нюанс в том, что в пустом списке нет максимального элемента, так что нужно вернуть nil. Условием завершения рекурсии будет список из одного элемента. Очевидно, что этот элемент и есть максимальный элемент.

И третье тело функции реализует шаг итерации на списке, содержащем больше одного элемента. Опять делим список на голову и хвост. Чтобы найти максимальный элемент, нужно сравнить голову с максимальным элементом хвоста.

Для списка [1, 3, 33, 42] стек вызовов будет выглядеть так:

list_max([1,3,33,42])
max(1, list_max([3,33,42]))
max(1, max(3, list_max([33,42])))
max(1, max(3, max(33, list_max([42]))))
max(1, max(3, max(33, 42)))
max(1, max(3, 42))
max(1, 42)
42

Пример 3

Реализуем функцию, которая меняет местами пары чисел в списке.

def swap_pair([]), do: []
def swap_pair([_]), do: raise "Can't swap a list with an odd number of elements"
def swap_pair([a, b | tail]) do
  [b, a | swap_pair(tail)]
end

swap_pair([1,2,3,4]) # [2, 1, 4, 3]
TR.swap_pair([1,2,3]) # ** (RuntimeError) Can't swap a list with an odd number of elements

Здесь две особенности. Во-первых, функция извлекает не одну голову из списка, а сразу две. Оператор | позволяет извлекать сразу несколько элементов. Во-вторых, функция предъявляет требование к входящим данным -- список должен иметь четное количество элементов.

Задание

Реализовать функцию range(from, to), которая принимает два числа, задающих диапазон, и возвращает список, заполненный числами в этом диапазоне, from и to включительно:

Solution.range(1, 5) # [1, 2, 3, 4, 5]
Solution.range(2, 2) # [2]
Solution.range(3, 2) # []
Упражнение не проходит проверку — что делать? 😶

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

  • Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.
В моей среде код работает, а здесь нет 🤨

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя 🤔

Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно 🙄

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.

Нашли ошибку? Есть что добавить? Пулреквесты приветствуются https://github.com/hexlet-basics
Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе