Пришло время переосмыслить обучение рекурсии с помощью реальных кейсов вместо элегантных математических уравнений
Для программистов, особенно программистов-самоучек, первое знакомство с миром «рекурсии» в основном связано с математикой. При упоминании рекурсии программисты сразу вспоминают некоторые из наших любимых слов на F – нет, не те самые слова на F, а:
Фибоначчи
function fibonacci(position) {
if (position < 3) return 1;
return fibonacci(position - 1) + fibonacci(position - 2);
}
Факториал
function factorial(num) {
if (num === 1) return num;
return num * factorial(num - 1);
}
Рекурсивные версии функций Фибоначчи и факториала – одни из самых красивых фрагментов кода, которые можно увидеть. Эти краткие фрагменты при выполнении работы полагаются лишь на самих себя. Они воплощают в себе определение рекурсии – функции, которая вызывает себя (вызов самой себя – это рекурсия). Меня совсем не удивляет тот факт, что функции Фибоначчи и факториалы инкапсулируют тему рекурсии наподобие разнообразных руководств, которые показывает пример работы кода на основе счётчиков или TODO-листов. Фибоначчи и факториалы настолько же тривиальны, как счётчики или TODO-листы.
Возможно, вы слышали выражение, что «все итерационные алгоритмы можно выразить рекурсивно». Другими словами, функция, использующая цикл, может быть переписана для использования самой себя. Теперь, если любой итерационный алгоритм может быть написан рекурсивно, то же самое должно быть верно и для обратного.
Примечание: итерационный алгоритм или функция – это алгоритм, который использует цикл для выполнения работы.
Давайте вернёмся к рекурсивной функции Фибоначчи и вместо этого запишем её как итеративную функцию Фибоначчи:
function fibonacci(index = 1) {
let sequence = [0, 1, 1];
if (index < 3) return 1;
for (let i = 2; i < index; i++) {
sequence.push(sequence[sequence.length - 1] + sequence[sequence.length - 2]);
}
return sequence[index];
}
Давайте возьмём рекурсивную функцию факториала и напишем её как итеративную функцию:
function factorial(num) {
if (num === 1) return 1;
for (let i = num — 1; i >= 1; i--) {
num = num * i;
}
return num;
}Оба подхода приводят к одному и тому же выводу. Если вы возьмёте одинаковые входные данные, то функции дадут один и тот же результат. Даже путь, по которому они прошли, возможно, один и тот же. Единственное различие заключается в метафорическом способе транспортировки, используемом на пути к получению результата.
Итак, если мы можем писать рекурсивные функции итеративно, зачем нам вообще нужно беспокоиться о рекурсии и какая от этого польза в программировании?
Основная причина, по которой мы используем рекурсию, – упрощение алгоритма до терминов, легко понятных большинству людей. Здесь важно отметить, что цель рекурсии (или, скорее, преимущество от рекурсии) состоит в том, чтобы сделать наш код более понятным. Однако важно знать, что рекурсия не является механизмом, который используется для оптимизации кода – скорее всего, это может иметь неблагоприятное влияние на производительность по сравнению с эквивалентной функцией, написанной итеративно.
Краткий вывод из этого: рекурсивные функции повышают читаемость кода для разработчиков, а итерационные функции оптимизируют производительность кода.
Во многих статьях и руководствах по рекурсии, которые я читал раньше, разочаровывает то, что они склоняются к осторожности и зацикливаются только на разговоре о таких функциях, как рекурсивные Фибоначчи или факториалы. Их рекурсивное написание не даёт разработчикам никаких реальных преимуществ. Это всё равно, что рассказать шутку без каких-либо предпосылок к ней.
Если преобразовать рекурсивные функции в итерационные, мы также получаем довольно неплохой код. Пожалуй, он так же легко читаем, как и его рекурсивные эквиваленты. Конечно, он может не иметь такого же уровня элегантности, но если он всё ещё читаем, я собираюсь пойти дальше и отдать предпочтение оптимизации кода, чем наоборот.
Поэтому кажется правдоподобным, что многие люди, впервые изучающие рекурсию, с трудом могут увидеть реальную пользу от её использования. Может быть, они просто видят в этом некую чрезмерную абстракцию. Так чем же полезна рекурсия? Или, ещё лучше, как мы можем сделать изучение рекурсии полезным?
Полезную рекурсию можно найти, когда мы на самом деле пытаемся написать код, напоминающий сценарий из реальной жизни.
Я могу сказать, что почти ни один разработчик где бы то ни было (за исключением написания кода на собеседования) не собирался реализовывать рекурсивную функцию Фибоначчи или факториальную функцию для своей работы, и, если бы это было нужно, он мог бы просто погуглить, так как есть миллион статей, объясняющих это.
Однако существует очень мало статей, демонстрирующих, как рекурсию можно использовать в реальных кейсах. Нам нужно меньше статей наподобие «Введение в рекурсию» и больше статей о том, как рекурсия может быть полезна в решении задач, с которыми вы столкнётесь на работе.
Итак, теперь, когда мы подошли к этой теме, давайте представим следующий кейс: ваш босс прислал вам структуру данных, состоящую из разных отделов, каждый из которых содержит E-mail всех, кто работает в этом отделе. Однако отдел может состоять из подразделений: объектов и массивов разного уровня. Ваш босс хочет, чтобы вы написали функцию, которая сможет отправлять электронное письмо на каждый из этих адресов электронной почты.
Вот структура данных:
const companyEmailAddresses = {
finance: ["jill@companyx.com", "frank@companyx.com"],
engineering: {
qa: ["ahmed@companyx.com", "taylor@companyx.com"],
development: ["cletus@companyx.com", "bojangles@companyx.com", "bibi@companyx.com"],
},
management: {
directors: ["tanya@companyx.com", "odell@companyx.com", "amin@companyx.com"],
projectLeaders: [
"bobby@companyx.com",
"jack@companyx.com",
"harry@companyx.com",
"oscar@companyx.com",
],
hr: ["mo@companyx.com", "jag@companyx.com", "ilaria@companyx.com"],
},
sales: {
business: {
senior: ["larry@companyx.com", "sally@companyx.com"],
},
client: {
senior: ["jola@companyx.com", "amit@companyx.com"],
exec: ["asha@companyx.com", "megan@companyx.com"],
},
},
};И как же с этим справиться?
Из того, что мы видим, подразделения записаны в объект, в то время как массивы используются для хранения адресов электронной почты. Поэтому можно попытаться написать какую-то итеративную функцию, которая проходит по каждому отделу и проверяет, является ли он отделом (объектом) или списком адресов электронной почты (массивом). Если это массив, мы можем перебрать массив и отправить электронное письмо на каждый адрес. Если это объект, можно создать ещё один цикл для работы с этим отделом, используя ту же тактику «проверить, является ли это объектом или массивом». Насколько мы можем видеть, наша структура данных не имеет больше двух подуровней. Так что еще одна итерация должна удовлетворить все уровни и сделать то, что мы хотим.
Наш окончательный код может выглядеть примерно так:
function sendEmail(emailAddress) {
console.log(`sending email to ${emailAddress}`);
}
function gatherEmailAddresses(departments) {
let departmentKeys = Object.keys(departments);
for (let i = 0; i < departmentKeys.length; i++) {
if (Array.isArray(departments[departmentKeys[i]])) {
departments[departmentKeys[i]].forEach((email) => sendEmail(email));
} else {
for (let dept in departments[departmentKeys[i]]) {
if (Array.isArray(departments[departmentKeys[i]][dept])) {
departments[departmentKeys[i]][dept].forEach((email) => sendEmail(email));
} else {
for (let subDept in departments[departmentKeys[i]][dept])
if (Array.isArray(departments[departmentKeys[i]][dept][subDept])) {
departments[departmentKeys[i]][dept][subDept].forEach((email) => sendEmail(email));
}
}
}
}
}
}
Я проверил вывод этого кода, может быть, я даже написал для него небольшой модульный тест. Этот код неразборчивый, но он работает. Учитывая количество вложенных циклов, можно утверждать, что он крайне неэффективен. А кто-то на заднем плане может кричать: «Big O? Больше похоже на Big OMG, верно?»
Конечно, есть и другие способы решения этой задачи, но то, что у нас есть на данный момент, работает. В любом случае, это всего лишь небольшая функция, и там не так много адресов электронной почты, и, вероятно, она не будет использоваться часто, так что это не имеет значения. Давайте вернёмся к работе над более важными проектами, прежде чем босс найдёт для меня еще одну побочную задачу!
Через пять минут ваш босс возвращается и говорит, что он также хочет, чтобы функция работала, даже если новые отделы, подразделения и адреса электронной почты будут добавлены в эту структуру данных. Это меняет ситуацию, потому что теперь мне нужно учитывать возможность наличия подподподразделений, подподподподразделений и так далее.
Внезапно итерационная функция больше не удовлетворяет критериям.
Но, о чудо, мы можем использовать рекурсию!
function sendEmail(emailAddress) {
console.log(`sending email to ${emailAddress}`);
}
function gatherEmailAddresses(departments) {
let departmentKeys = Object.keys(departments);
departmentKeys.forEach((dept) => {
if (Array.isArray(departments[dept])) {
return departments[dept].forEach((email) => sendEmail(email));
}
return gatherEmailAddresses(departments[dept]);
});
}Итак, наконец-то у нас есть функция, которая использует рекурсию в более-менее реальном кейсе. Давайте разберёмся, как это всё работает.
Наша функция перебирает ключи из
companyEmailAddresses, проверяет, является ли значение этого ключа массивом, и если да, то отправляет электронное письмо каждому значению в этом массиве. Однако, если значение вышеупомянутого ключа не является массивом, она снова вызовет себя – gatherEmailAddresses (функция рекурсивно выполняется). Однако вместо того чтобы передавать весь объект companyEmailAddresses, как это было в первый раз, функция просто передаст узел объекта для подкаталога, через который он изначально проходил в цикле.Эта функция имеет два преимущества по сравнению с нашим предыдущим итеративным аналогом:
Она соответствует дополнительным критериям, установленным нашим начальником. Пока функция продолжает следовать тому же шаблону, она может обрабатывать любые новые объекты или массивы, добавленные к ней, без необходимости изменять ни одной строчки кода;
Код легко читаем. У нас нет набора вложенных циклов, которые наш мозг должен попытаться отслеживать.
Также можно заметить, что наша функция на самом деле содержит итеративные и рекурсивные элементы. Нет причин, по которым алгоритм должен быть исключительно тем или иным. Совершенно нормально иметь что-то итеративное, например функцию forEach, содержащую рекурсивные вызовы самой себя.
Давайте на мгновение вернёмся ко второму пункту. Функцию будет легче читать, только если вы поймёте, как работает рекурсия вне рамок Фибоначчи, факториала и любых других подобных функций, которые можно найти в книге/курсе «To Crack The Coding Interview». Итак, давайте немного углубимся в то, что именно происходит внутри нашей рекурсивной функции.
Наша функция принимает в качестве единственного параметра одно значение – объект. Передаваемый объект – это переменная
companyEmailAddresses, представляющая собой гротескного монстра:const companyEmailAddresses = {
finance: ["jill@companyx.com", "frank@companyx.com"],
engineering: {
qa: ["ahmed@companyx.com", "taylor@companyx.com"],
development: ["cletus@companyx.com", "bojangles@companyx.com", "bibi@companyx.com"],
},
management: {
directors: ["tanya@companyx.com", "odell@companyx.com", "amin@companyx.com"],
projectLeaders: [
"bobby@companyx.com",
"jack@companyx.com",
"harry@companyx.com",
"oscar@companyx.com",
],
hr: ["mo@companyx.com", "jag@companyx.com", "ilaria@companyx.com"],
},
sales: {
business: {
senior: ["larry@companyx.com", "sally@companyx.com"],
},
client: {
senior: ["jola@companyx.com", "amit@companyx.com"],
exec: ["asha@companyx.com", "megan@companyx.com"],
},
},
};
Первое, что мы делаем с ним, – это выполняем метод Object.keys(), который возвращает массив с каждым отделом. Примерно так:
["finance", "engineering", "management", "sales"]. Затем мы проходим по companyEmailAddresses с помощью forEach, используя массив отделов как способ проверить каждый отдел на предмет определённых вещей. В нашем случае мы используем его, чтобы проверить, является ли структура каждого узла массивом или нет, что мы делаем с помощью метода Array.isArray(departments[dept]). Если он возвращает true, мы просто переходим к перебору этого массива, вызывая функцию sendEmail() для каждого значения. Достаточно простая реализация, а до сих пор мы не использовали рекурсию. Возможно, вам даже не нужно было читать этот абзац, но по крайней мере это объяснение здесь есть, если оно вам действительно нужно. В любом случае давайте перейдем к интересному – рекурсии.Если наш метод
Array.isArray(departments[dept]) возвращает false, это означает, что мы получили объект, следовательно, он является подразделением. В нашей итеративной функции мы просто повторяли процесс, т. е. выполнили еще один цикл, но сделали это для подразделения. Но вместо этого в рекурсивной функции мы снова вызываем функцию gatherEmailAddresses(), передавая тот же объект companyEmailAddresses, что и раньше. Ключевое отличие здесь в том, что вместо передачи объекта из его корня (весь объект), мы передаём его с позиции подкаталога, где подкаталог становится новым корнем. Мы знаем, что наш объект companyEmailAddresses просто состоит из множества объектов, которые содержат либо объект, либо массив. Поэтому наша функция была написана таким образом, что если она получит массив, она знает, что это конец узла, поэтому она будет пытаться «отправить электронные письма». Но если она попадает в объект, ей нужно продолжать работу.Имеет смысл?
Вот несколько структур, которые я написал, чтобы попытаться пояснить их в дальнейшем.
Весь наш объект состоит из четырёх отделов. Первый отдел – это массив. Дополнительного обхода не требуется, поскольку мы сразу попали в листовой узел. Этот отдел вернёт
true в Array.isArray(). finance: [
"jill@companyx.com",
"frank@companyx.com"
],Второй отдел – это объект. Этот отдел вернёт
false в Array.isArray(). Это требует дополнительного обхода, поэтому мы вызываем функцию gatherEmailAddresses(), передавая department[dept], что эквивалентно companyEmailAddresses["engineering"] или коду, который вы видите ниже.engineering: {
qa: [
"ahmed@companyx.com",
"taylor@companyx.com"
],
development: [
"cletus@companyx.com",
"bojangles@companyx.com",
"bibi@companyx.com"
],
},Поскольку мы снова рекурсивно вызвали нашу функцию, мы пока не переходим к третьему отделу, поскольку наша рекурсивная функция должна обрабатываться первой, то есть мы всё ещё обрабатываем второй отдел. Технический способ объяснить это заключается в том, что наш рекурсивный вызов добавляется в наш стек вызовов.
Как вы помните, первое, что делает наша функция, – это вызывает
Object.keys() для переданного объекта. Это выдаст нам ["qa", "development"]. Затем мы перебираем каждый отдел (или, в данном случае, подразделение). Мы проверяем, является ли отдел/подразделение ‘qa’ массивом с помощью Array.isArray(). Да, является, поэтому мы вернем true, следовательно мы можем использовать функцию sendEmail(). То же самое может произойти и с "development", поскольку это тоже массив.engineering: {
qa: [
"ahmed@companyx.com",
"taylor@companyx.com"
],
development: [
"cletus@companyx.com",
"bojangles@companyx.com",
"bibi@companyx.com"
],
},Третий отдел (третье подразделение) имеет аналогичную структуру со вторым отделом (второе подразделение), в то время как четвёртый отдел имеет еще два отдела, а эти два отдела также содержат очередные два отдела — а наша рекурсивная функция проходит по каждому из них. Я не приложил фрагмент кода для этого случая, поскольку считаю, что вы уже поняли, как работает рекурсия.
Заключение
Итак, мы рассмотрели пример рекурсии на практике. Надеюсь, это дало вам более глубокое понимание рекурсии, а также вы узнали один способ решения задач, требующих определённого цикла.
Однако я хотел бы еще раз подчеркнуть: если вы используете рекурсию, производительность кода может снизиться, хотя этого не должно быть. Рекурсия не должна внезапно стать вашим привычным инструментом вместо итерации. Выгода, которую вы добились в читаемости кода, может быть потеряна в его производительности. В конечном счёте это зависит от представленной вам задачи. Вы столкнётесь с некоторыми задачами в программировании, которые могут хорошо подойти для рекурсии, в то время как другие задачи могут лучше подойти для итераций. В некоторых случаях, например в задаче, с которой мы столкнулись ранее, лучше всего использовать оба подхода. А если вы уже давно выучили рекурсию и хотите новых знаний, например в области Data Science или Machine Learning — используйте промокод HABR, который дает +10% к скидке на обучение, указанной ниже на баннере.
Другие профессии и курсы
ПРОФЕССИИ
КУРСЫ
- Профессия Java-разработчик
- Профессия QA-инженер на JAVA
- Профессия Frontend-разработчик
- Профессия Этичный хакер
- Профессия C++ разработчик
- Профессия Разработчик игр на Unity
- Профессия Веб-разработчик
- Профессия iOS-разработчик с нуля
- Профессия Android-разработчик с нуля
КУРСЫ
- Курс по Data Engineering
- Курс по Machine Learning
- Курс «Математика и Machine Learning для Data Science»
- Курс «Python для веб-разработки»
- Курс «Алгоритмы и структуры данных»
- Курс по аналитике данных
- Курс по DevOps
