Elixir: Рекурсия

• Пример 1
• Пример 2
• Пример 3

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

Пример 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) # []

Полезное

• Статья в Hexlet про рекурсию