Я хочу избавить рекурсивные функции от некоторого страха.
Слово «рекурсивный» использовалось, чтобы заставить мой разум отключиться от того, как математические термины в старшей школе походили на «квадратические функции» или «полиномы».
Каждый раз, когда я читал что-то, связанное с рекурсией, я искал более простое решение в другом месте.
Теперь я смотрю на них как на инструмент, который иногда легче осмыслить, чем копаться в некоторых функциях 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
, когда вам нужно создать какой-то цикл.
Тем не менее, рекурсивные функции могут быть лучшим инструментом для работы, когда вам нужно отслеживать несколько разных переменных во время прохождения цикла, и хотя мы не рассматривали здесь никаких примеров этого, надеюсь, это обеспечивает основу. так что более сложные примеры в другом месте будут иметь смысл.
Я часто использую рекурсивные функции при кодировании вопросов типа собеседований, и не очень часто в реальных проектах. Ваш опыт может быть другим!
Если вы хотите глубже понять, как работают рекурсивные функции (теперь, когда они больше не пугают!), Ознакомьтесь со следующими ресурсами:
- Официальные гиды
- Программирование на Эликсире 1.6 (очень рекомендую эту книгу)
- Школа Эликсира
- Быстрый поиск в Google по запросу «Рекурсивная функция Эликсира»
Спасибо за чтение!