Я хочу избавить рекурсивные функции от некоторого страха.

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

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

Теперь я смотрю на них как на инструмент, который иногда легче осмыслить, чем копаться в некоторых функциях reduce в модуле Enum.

Итак, как мне убедить вас, что рекурсивные функции не страшны?

Давайте посмотрим на нормальную функцию:

def normal_function(number) do
  number + 1
end

Все, что делает normal_function/1, это принимает число и затем добавляет к нему 1.

Теперь давайте посмотрим на другую нормальную функцию:

def also_normal(number) do
  new_number = number + 1
  other_function(new_number)
end
def other_function(number) do
  number
end

В этой also_normal/1 функции мы берем число в качестве аргумента и добавляем к нему 1, а затем передаем его в качестве аргумента в other_function/1.

Функция also_normal/1 не связана с тем, что other_function/1 делает с числом, она просто вызывает функцию и передает new_number, и все готово.

Теперь давайте посмотрим на (плохую, бесконечно повторяющуюся) рекурсивную функцию:

def bad_recursive_function(number) do
  new_number = number + 1
  bad_recursive_function(new_number)
end

Эта функция во многом похожа на функцию also_normal/1: она принимает число и добавляет к нему 1. Затем он вызывает функцию с новым номером.

Единственное отличие состоит в том, что вместо вызова * другой * функции она вызывает * себя * и передает новый номер.

Это определение рекурсивной функции: функция, которая вызывает сама себя.

Если вы действительно запустили этот код (пожалуйста, не запускайте), он будет работать вечно. Каждый раз, когда функция запускалась, она вызывала себя снова и снова, каждый раз добавляя к номеру 1, и она никогда не прекращала добавлять.

Чтобы остановить эту рекурсивную функцию, нам понадобится еще одно функциональное предложение:

def better_recursive_function(100) do
  100
end
def better_recursive_function(number) do
  new_number = number + 1
  better_recursive_function(new_number)
end

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

Если мы запустим better_recursive_function(100), верхнее предложение будет соответствовать, и оно немедленно вернет 100 и будет выполнено.

Это верхнее предложение, которое останавливает цикл, называется «базовым случаем» или «якорным случаем».

Если мы запустим better_recursive_function(98), верхнее предложение не будет совпадать, поэтому он попробует второе предложение, которое будет соответствовать. К номеру 98 будет добавлено 1, и better_recursive_function/1 будет вызываться снова с new_number, который теперь равен 99.

Опять же, верхнее предложение не будет соответствовать, но второе будет, поэтому функция вызывается в последний раз с new_number равным 100. Верхнее предложение совпадает, и все готово!

Это лучше, потому что функция может действительно останавливаться, но это по-прежнему небезопасно (вы будете тостом, если передадите число больше 100), и это тоже не очень полезно.

Давайте быстро создадим надуманную проблему, а затем решим ее с помощью рекурсивной функции, которая очень похожа на нашу better_recursive_function/1.

Быстрый:

Вам нужна функция, которая принимает любое положительное целое число и округляет его до ближайшего кратного 10.

Итак, если вы передадите 41, он должен вернуть 50. Если вы пройдете 78, вы вернетесь 80.

Решение:

Во-первых, давайте обсудим, как мы собираемся подойти к проблеме.

Нам нужен «базовый» или «якорный» кейс, который остановит функцию от вызова самой себя навсегда. Поскольку нам нужно остановить цикл, когда у нас есть число, кратное 10, мы позаботимся о том, чтобы наш базовый случай соответствовал, когда у нас есть число, кратное 10, например:

def next_multiple_of_ten(number) when rem(number, 10) == 0 do
  number
end

Теперь, ниже базового случая, мы можем использовать ту же рекурсивную функцию, которую мы использовали все время, которая добавляет 1 к числу, а затем вызывает себя снова!

def next_multiple_of_ten(number) when rem(number, 10) == 0 do
  number
end
def next_multiple_of_ten(number) do
  new_number = number + 1
  next_multiple_of_ten(new_number)
end

Теперь у нас есть настоящая (и полезная!) Рекурсивная функция!

Мысли на прощание

Есть много аспектов рекурсивных функций, которые я не рассмотрел.

Большую часть времени в повседневном кодировании вы будете обращаться к функциям модуля Enum, когда вам нужно создать какой-то цикл.

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

Я часто использую рекурсивные функции при кодировании вопросов типа собеседований, и не очень часто в реальных проектах. Ваш опыт может быть другим!

Если вы хотите глубже понять, как работают рекурсивные функции (теперь, когда они больше не пугают!), Ознакомьтесь со следующими ресурсами:

Спасибо за чтение!