Как работает рекурсия – объяснение в блок-схемах и видео
Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.
«Для того чтобы понять рекурсию, надо сначала понять рекурсию»
Рекурсию порой сложно понять, особенно новичкам в программировании. Если говорить просто, то рекурсия – это функция, которая сама вызывает себя. Но давайте попробую объяснить на примере.
Представьте, что вы пытаетесь открыть дверь в спальню, а она закрыта. Ваш трехлетний сынок появляется из-за угла и говорит, что единственный ключ спрятан в коробке. Вы опаздываете на работу и Вам действительно нужно попасть в комнату и взять вашу рубашку.
Вы открываете коробку только чтобы найти… еще больше коробок. Коробки внутри коробок и вы не знаете, в какой из них Ваш ключ. Вам срочно нужна рубашка, так что вам надо придумать хороший алгоритм и найти ключ.
Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:
Какой подход для Вас проще?
В первом подходе используется цикл while. Т.е. пока стопка коробок полная, хватай следующую коробку и смотри внутрь нее. Ниже немного псевдокода на Javascript, который отражает то, что происходит (Псевдокод написан как код, но больше похожий на человеческий язык).
В другом подходе используется рекурсия. Помните, рекурсия – это когда функция вызывает саму себя. Вот второй вариант в псевдокоде:
Оба подхода выполняют одно и тоже. Основный смысл в использовании рекурсивного подхода в том, что однажды поняв, вы сможете легко его читать. В действительности нет никакого выигрыша в производительности от использования рекурсии. Порой итеративный подход с циклами будет работать быстрее, но простота рекурсии иногда предпочтительнее.
Поскольку рекурсия используется во многих алгоритмах, очень важно понять как она работает. Если рекурсия до сих пор не кажется Вам простой, не беспокойтесь: Я собираюсь пройтись еще по нескольким примерам.
Граничный и рекурсивный случай
То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:
Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)
Рекурсивная функция всегда должна знать, когда ей нужно остановиться. В рекурсивной функции всегда есть два случая: рекурсивный и граничный случаи. Рекурсивный случай – когда функция вызывает саму себя, а граничный – когда функция перестает себя вызывать. Наличие граничного случая и предотвращает зацикливание.
И снова функция подсчета, только уже с граничным случаем:
То, что происходит в этой функции может и не быть абсолютно очевидным. Я поясню, что произойдет, когда вы вызовете функцию и передадите в нее цифру 5.
Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).
Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.
Стек вызовов
Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.
Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:
Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3). Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact, на которой вы остановились в данный момент:
Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.
Нашли уже ключ?
Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.
Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!
И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!
Вы также можете посмотреть мое пятиминутное видео про рекурсию. Оно должно усилить понимание, приведенных здесь концепций.
Заключение от автора
Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.
И наконец, чтобы действительно закрепить свои знания о рекурсии, Вы должны прочитать эту статью, как минимум, еще раз.
От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».
Функциональное программирование с точки зрения EcmaScript. Рекурсия и её виды
Сегодня мы продолжим наши изыскания на тему функционального программирования в разрезе EcmaScript, на спецификации которого основан JavaScript. В предыдущих статьях цикла были рассмотрены следующие темы:
Рекурсия
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее применение находит в математике и информатике.
Применительно к программированию под рекурсией подразумевают процессы, которые вызывают сами себя в своём теле. Рекурсивная функция имеет несколько обязательных составляющих:
Выделим характерные составляющие рекурсивной функции. Терминальное условие
и правило движения по рекурсии
Важно осознавать, что рекурсия это не какая-то специфическая фича JS, а техника очень распространённая в программировании.
Рекурсивный и итеративный процессы
Рекурсию можно организовать двумя способами: через рекурсивный процесс или через итеративный.
Рекурсивный процесс мы с вами уже видели:
Итеративное решение задачи о факториале выглядело бы так:
Оба этих варианта это рекурсия. В обоих решениях есть характерные для рекурсии черты: терминальное условие и правило движения по рекурсии. Давайте разберём их отличия.
Рекурсивный процесс на каждом шаге запоминает действие. которое надо сделать. Дойдя до термального условия, он выполняет все запомненные действия в обратном порядке. Поясним на примере. Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вглубь больше нельзя. Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.
Выглядит это примерно так:
Как видите, основная идея рекурсивного процесса — откладывание вычисления до конца.
Такой процесс порождает изменяемое во времени состояние, которое хранится «где-то» снаружи текущего вызова функции.
Думаю, вы помните, что в первой статье из цикла о Функциональном программировании мы говорили о важности имутабельности и отсутствия состояния. Наличие состояния порождает много проблем, с которыми не всегда легко справится.
Итеративный процесс отличается от рекурсивного фиксированным количеством состояний. На каждом своём шаге итеративный процесс считает всё, что может посчитать, поэтому каждый шаг рекурсии существует независимо от предыдущего.
Думаю, очевидно, что итеративный процесс потребляет меньше памяти. Следовательно, всегда при создании рекурсии следует использовать его. Единственное исключение: если мы не можем посчитать значение до достижения термального условия.
Древовидная рекурсия
Многие считают, что деревья и работа с ними это что-то очень заумное, сложное и не понятное простым смертным. На самом деле это не так. Любая иерархическая структура может быть представлена в виде дерева. Даже человеческое мышление подобно дереву.
Чтобы лучше понять древовидную рекурсию разберём простой и популярный пример — числа Фибоначчи.
Чи́сла Фибона́ччи — элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (последовательность A000045 в OEIS), в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).
Математически довольно просто сформулировать описание (а ведь декларативное программирование и есть описание) данной последовательности:
Теперь давайте перейдём от математики к логическим рассуждениям(нам ведь нужно программную логику написать). Для вычисления fib(5) нам придётся вычислить fib(4) и fib(3). Для вычисления fib(4) нам придётся вычислить fib(3) и fib(2). Для вычисления fib(3) нам придётся вычислить fib(2) и так до тех пор пока мы не дойдём до известных значений (1) и (2) в нашей математической модели.
На какие мысли нас должны навести наши рассуждения? Очевидно, мы должны использовать рекурсию. Термальное условие можно сформулировать как n
Рекурсия. Занимательные задачки
В этой статье речь пойдет о задачах на рекурсию и о том как их решать. 
Кратко о рекурсии
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.
В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).
Задачи
При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно.
Для обоснования можно привести такие доводы.
Для начала можно вспомнить определение рекурсии и итерации. Рекурсия — это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ. Итерация — это способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.
После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий — итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно — завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.
Задача по приведению рекурсии к итеративному подходу симметрична.
Подводя итог, можно выразить такие мысли: для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче.
Более подробно с этим можно познакомиться тут
Так же как и у перебора (цикла) у рекурсии должно быть условие остановки — Базовый случай (иначе также как и цикл рекурсия будет работать вечно — infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.
В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня
Рассмотрим же теперь задачи с различным уровнем сложности.
Попробуйте их решить самостоятельно используя метод описанный выше. При решении попробуйте думать рекурсивно. Какой базовый случай в задаче? Какой Шаг рекурсии или рекурсивное условие?
Поехали! Решения задач предоставлены на языке Java.
A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.
Рекурсия. Беглый взгляд
Ниже речь пойдёт о старушке рекурсии, которую неплохо бы представлять, понимать и применять.
Примечание: Данная небольшая статья написана для беглого ознакомления с рекурсией, некоторыми примерами её применения и опасностями.
Определение
Для начала стоит сказать, что рекурсия относится не только к программированию. Рекурсия — это общее понятие, которое может быть присуще чему угодно и встречаться в повседневной жизни, но больше всего она распространена в информатике и математике. Для программистов же умение применять рекурсию — большой плюс в коллекцию полезных навыков.
Самая большая глупость — это делать то же самое и надеяться на другой результат.
Под рекурсией понимают процесс повторения элементов самоподобным образом. Объект обладает рекурсией, если он является частью самого себя.
Частным случаем рекурсии является хвостовая рекурсия. Если любой рекурсивный вызов является последней операцией перед возвратом из функции, то это оно.
Некоторые примеры
Рекурсию надо бы понять, а определение для этого подходит хуже, чем наглядные примеры. Для лучшего понимания, конечно, всё же следует прочитать определение, посмотреть на пример, снова прочитать определение и снова посмотреть на пример… Повторять, пока не придёт осознание.
Отличный пример вы можете найти тут.
Самое известное программисту применение рекурсии — задачи на вычисление чисел Фибоначчи или факториала. Давайте покажем, как это реализовать на языке C:
Тут же стоит отметить, что декларативная парадигма, в частности парадигма логического программирования, намного лучше позволяет понять рекурсию, так как там это обычное дело.
Fork-бомба
Примечание: Рекурсивное создание процессов крайне быстро (из-за экспоненциального роста их количества) заполняет таблицу процессов, что достаточно опасно для системы.
Reboot кнопкой после такого делать немного не приятно.
Для математика первой ассоциацией, скорее всего, будет фрактал. Фракталы прекрасны и приятно для глаза показывают свойства самоподобия.
Самые известные фракталы:
Ну и в повседневной жизни классическим примером являются два зеркала, поставленных друг напротив друга.
Углубимся глубже
Проста ли рекурсия? Однозначно нет. На вид кажется, что всё просто, однако рекурсия таит в себе опасности (А иногда она просто не понятна).
Вернёмся к примеру с вычислением чисел Фибоначчи. Сразу заметим, что возвращаемым результатом функции является вызов этой же функции, а если быть точнее, то сумма результатов вызова двух функций (именно поэтому рекурсия не хвостовая). Становится понятно, что второй вызов не произойдёт, пока не завершится первый (в котором также будет вызов двух функций). Тут же пытливый ум заметит, что из рекурсивной функции должен существовать «нормальный» выход, без самовызова, иначе мы познакомимся с переполнением стека вызовов — это один из ключевых моментов, который стоит держать в голове при работе с функциями вызывающими сами себя.
Заметим, что дерево вызовов получится большим, но максимальное количество вызовов в стеке будет заметно меньше (N-1 при N > 2, соответственно).
Рекурсивные алгоритмы довольно-таки часто встречаются при работе с деревьями, сортировками и задачами на графах. Так что, чтобы лучше вникнуть нужна практика и для этого не плохо подходит вышеупомянутое (в частности, бинарные или общие деревья. Их реализация не так сложна, а опыт работы с рекурсией получится не плохой).
Помимо этого хотелось бы упомянуть Ханойские башни, которые также отлично подойдут для ознакомления с рекурсивными задачами. На Хабре также был отличный разбор этой игры.
Для полноты картины обязательно надо упомянуть о борьбе с рекурсией.
Повышается производительность. Но это не значит, что с ней просто необходимо бороться, ведь применение рекурсии очевиднее, проще и приятнее, чем итерационные варианты.
Под силу ли побороть любую рекурсию?
Однозначно да. Любой рекурсивный алгоритм можно переписать без использования рекурсии, а хвостовую рекурсию же очень легко перевести на итерацию (чем и занимаются некоторые компиляторы для оптимизации). Это также относится и к итерационным алгоритмам.
Самый известный способ — это использование стека. Здесь подробнее, для интересующихся.
Заключение
Спасибо за прочтение статьи. Надеюсь, что большинство не знакомых с рекурсией получили базовое представление о ней, а от знающих людей, конечно, хочется услышать дополнения и замечания в комментариях. Не бойтесь рекурсии и не переполняйте стек!
UPD: Добавлен корректный пример хвостовой рекурсии.
Как учить рекурсию разработчикам программного обеспечения
Пришло время переосмыслить обучение рекурсии с помощью реальных кейсов вместо элегантных математических уравнений
Для программистов, особенно программистов-самоучек, первое знакомство с миром «рекурсии» в основном связано с математикой. При упоминании рекурсии программисты сразу вспоминают некоторые из наших любимых слов на F – нет, не те самые слова на F, а:
Фибоначчи
Факториал
Рекурсивные версии функций Фибоначчи и факториала – одни из самых красивых фрагментов кода, которые можно увидеть. Эти краткие фрагменты при выполнении работы полагаются лишь на самих себя. Они воплощают в себе определение рекурсии – функции, которая вызывает себя (вызов самой себя – это рекурсия). Меня совсем не удивляет тот факт, что функции Фибоначчи и факториалы инкапсулируют тему рекурсии наподобие разнообразных руководств, которые показывает пример работы кода на основе счётчиков или TODO-листов. Фибоначчи и факториалы настолько же тривиальны, как счётчики или TODO-листы.
Возможно, вы слышали выражение, что «все итерационные алгоритмы можно выразить рекурсивно». Другими словами, функция, использующая цикл, может быть переписана для использования самой себя. Теперь, если любой итерационный алгоритм может быть написан рекурсивно, то же самое должно быть верно и для обратного.
Примечание: итерационный алгоритм или функция – это алгоритм, который использует цикл для выполнения работы.
Давайте вернёмся к рекурсивной функции Фибоначчи и вместо этого запишем её как итеративную функцию Фибоначчи:
Давайте возьмём рекурсивную функцию факториала и напишем её как итеративную функцию:
Оба подхода приводят к одному и тому же выводу. Если вы возьмёте одинаковые входные данные, то функции дадут один и тот же результат. Даже путь, по которому они прошли, возможно, один и тот же. Единственное различие заключается в метафорическом способе транспортировки, используемом на пути к получению результата.
Итак, если мы можем писать рекурсивные функции итеративно, зачем нам вообще нужно беспокоиться о рекурсии и какая от этого польза в программировании?
Основная причина, по которой мы используем рекурсию, – упрощение алгоритма до терминов, легко понятных большинству людей. Здесь важно отметить, что цель рекурсии (или, скорее, преимущество от рекурсии) состоит в том, чтобы сделать наш код более понятным. Однако важно знать, что рекурсия не является механизмом, который используется для оптимизации кода – скорее всего, это может иметь неблагоприятное влияние на производительность по сравнению с эквивалентной функцией, написанной итеративно.
Краткий вывод из этого: рекурсивные функции повышают читаемость кода для разработчиков, а итерационные функции оптимизируют производительность кода.
Во многих статьях и руководствах по рекурсии, которые я читал раньше, разочаровывает то, что они склоняются к осторожности и зацикливаются только на разговоре о таких функциях, как рекурсивные Фибоначчи или факториалы. Их рекурсивное написание не даёт разработчикам никаких реальных преимуществ. Это всё равно, что рассказать шутку без каких-либо предпосылок к ней.
Если преобразовать рекурсивные функции в итерационные, мы также получаем довольно неплохой код. Пожалуй, он так же легко читаем, как и его рекурсивные эквиваленты. Конечно, он может не иметь такого же уровня элегантности, но если он всё ещё читаем, я собираюсь пойти дальше и отдать предпочтение оптимизации кода, чем наоборот.
Поэтому кажется правдоподобным, что многие люди, впервые изучающие рекурсию, с трудом могут увидеть реальную пользу от её использования. Может быть, они просто видят в этом некую чрезмерную абстракцию. Так чем же полезна рекурсия? Или, ещё лучше, как мы можем сделать изучение рекурсии полезным?
Полезную рекурсию можно найти, когда мы на самом деле пытаемся написать код, напоминающий сценарий из реальной жизни.
Я могу сказать, что почти ни один разработчик где бы то ни было (за исключением написания кода на собеседования) не собирался реализовывать рекурсивную функцию Фибоначчи или факториальную функцию для своей работы, и, если бы это было нужно, он мог бы просто погуглить, так как есть миллион статей, объясняющих это.
Однако существует очень мало статей, демонстрирующих, как рекурсию можно использовать в реальных кейсах. Нам нужно меньше статей наподобие «Введение в рекурсию» и больше статей о том, как рекурсия может быть полезна в решении задач, с которыми вы столкнётесь на работе.
Итак, теперь, когда мы подошли к этой теме, давайте представим следующий кейс: ваш босс прислал вам структуру данных, состоящую из разных отделов, каждый из которых содержит E-mail всех, кто работает в этом отделе. Однако отдел может состоять из подразделений: объектов и массивов разного уровня. Ваш босс хочет, чтобы вы написали функцию, которая сможет отправлять электронное письмо на каждый из этих адресов электронной почты.
Вот структура данных:
И как же с этим справиться?
Из того, что мы видим, подразделения записаны в объект, в то время как массивы используются для хранения адресов электронной почты. Поэтому можно попытаться написать какую-то итеративную функцию, которая проходит по каждому отделу и проверяет, является ли он отделом (объектом) или списком адресов электронной почты (массивом). Если это массив, мы можем перебрать массив и отправить электронное письмо на каждый адрес. Если это объект, можно создать ещё один цикл для работы с этим отделом, используя ту же тактику «проверить, является ли это объектом или массивом». Насколько мы можем видеть, наша структура данных не имеет больше двух подуровней. Так что еще одна итерация должна удовлетворить все уровни и сделать то, что мы хотим.
Наш окончательный код может выглядеть примерно так:
Я проверил вывод этого кода, может быть, я даже написал для него небольшой модульный тест. Этот код неразборчивый, но он работает. Учитывая количество вложенных циклов, можно утверждать, что он крайне неэффективен. А кто-то на заднем плане может кричать: «Big O? Больше похоже на Big OMG, верно?»
Конечно, есть и другие способы решения этой задачи, но то, что у нас есть на данный момент, работает. В любом случае, это всего лишь небольшая функция, и там не так много адресов электронной почты, и, вероятно, она не будет использоваться часто, так что это не имеет значения. Давайте вернёмся к работе над более важными проектами, прежде чем босс найдёт для меня еще одну побочную задачу!
Через пять минут ваш босс возвращается и говорит, что он также хочет, чтобы функция работала, даже если новые отделы, подразделения и адреса электронной почты будут добавлены в эту структуру данных. Это меняет ситуацию, потому что теперь мне нужно учитывать возможность наличия подподподразделений, подподподподразделений и так далее.
Внезапно итерационная функция больше не удовлетворяет критериям.
Но, о чудо, мы можем использовать рекурсию!
Итак, наконец-то у нас есть функция, которая использует рекурсию в более-менее реальном кейсе. Давайте разберёмся, как это всё работает.
Эта функция имеет два преимущества по сравнению с нашим предыдущим итеративным аналогом:
Она соответствует дополнительным критериям, установленным нашим начальником. Пока функция продолжает следовать тому же шаблону, она может обрабатывать любые новые объекты или массивы, добавленные к ней, без необходимости изменять ни одной строчки кода;
Код легко читаем. У нас нет набора вложенных циклов, которые наш мозг должен попытаться отслеживать.
Также можно заметить, что наша функция на самом деле содержит итеративные и рекурсивные элементы. Нет причин, по которым алгоритм должен быть исключительно тем или иным. Совершенно нормально иметь что-то итеративное, например функцию forEach, содержащую рекурсивные вызовы самой себя.
Давайте на мгновение вернёмся ко второму пункту. Функцию будет легче читать, только если вы поймёте, как работает рекурсия вне рамок Фибоначчи, факториала и любых других подобных функций, которые можно найти в книге/курсе «To Crack The Coding Interview». Итак, давайте немного углубимся в то, что именно происходит внутри нашей рекурсивной функции.
Вот несколько структур, которые я написал, чтобы попытаться пояснить их в дальнейшем.
Поскольку мы снова рекурсивно вызвали нашу функцию, мы пока не переходим к третьему отделу, поскольку наша рекурсивная функция должна обрабатываться первой, то есть мы всё ещё обрабатываем второй отдел. Технический способ объяснить это заключается в том, что наш рекурсивный вызов добавляется в наш стек вызовов.
Третий отдел (третье подразделение) имеет аналогичную структуру со вторым отделом (второе подразделение), в то время как четвёртый отдел имеет еще два отдела, а эти два отдела также содержат очередные два отдела — а наша рекурсивная функция проходит по каждому из них. Я не приложил фрагмент кода для этого случая, поскольку считаю, что вы уже поняли, как работает рекурсия.
Заключение
Итак, мы рассмотрели пример рекурсии на практике. Надеюсь, это дало вам более глубокое понимание рекурсии, а также вы узнали один способ решения задач, требующих определённого цикла.
Однако я хотел бы еще раз подчеркнуть: если вы используете рекурсию, производительность кода может снизиться, хотя этого не должно быть. Рекурсия не должна внезапно стать вашим привычным инструментом вместо итерации. Выгода, которую вы добились в читаемости кода, может быть потеряна в его производительности. В конечном счёте это зависит от представленной вам задачи. Вы столкнётесь с некоторыми задачами в программировании, которые могут хорошо подойти для рекурсии, в то время как другие задачи могут лучше подойти для итераций. В некоторых случаях, например в задаче, с которой мы столкнулись ранее, лучше всего использовать оба подхода. А если вы уже давно выучили рекурсию и хотите новых знаний, например в области Data Science или Machine Learning — используйте промокод HABR, который дает +10% к скидке на обучение, указанной ниже на баннере.
