Вы когда-нибудь сталкивались с необходимостью перебрать сложный многомерный объект в JavaScript и не знали, как это сделать? В таком случае стоит воспользоваться Google как мощным инструментом для поиска решения. Однако, поскольку вы здесь, если продолжите читать, то, возможно, найдёте элегантное решение этой проблемы.
Давайте возьмём для примера такое дерево:
Задача: необходимо вывести в консоль имя каждого узла, включая корневой.
Когда мы впервые сталкиваемся с подобными задачами, мы часто попадаем под влияние эффекта Даннинга-Крюгера и думаем, что это можно решить с помощью простого цикла for. Короткий ответ: да… Но также нет, это не всегда лучший подход.
Давайте посмотрим, что происходит, когда мы следуем этому подходу:
Как вы можете видеть, хотя это и сработало, у такого решения есть несколько проблем:
- Во-первых, код сложно читать. Никто не хочет видеть кучу вложенных циклов в своём коде, а вы ведь командный игрок, верно?
- Что произойдёт, если это дерево должно измениться во время выполнения? Текущая реализация не динамична, поэтому вам придётся изменять код и добавлять дополнительные вложенные циклы вручную. Это может сделать код менее читаемым и поддерживаемым.
Именно здесь на помощь приходит рекурсия.
Что такое рекурсивная функция?
Это функция, которая вызывает саму себя во время выполнения. Эта характеристика позволяет использовать её для решения задач, которые можно разбить на более мелкие и простые подзадачи, идентичные общей проблеме.
Простой способ визуализировать это — функция обратного отсчёта с использованием рекурсии. Давайте посмотрим.
В этом примере функция countDownFrom выводит число, затем вызывает саму себя (рекурсия) с переданным числом минус один, повторяя этот процесс, пока не достигнет базового случая (в данном случае, когда n меньше 0).
Как видите, это, по сути, цикл, но более простой и элегантный.
Возвращаемся к нашему дереву
Наша первоначальная задача — вывести все имена узлов дерева, и мы будем использовать рекурсию для её решения, поскольку заметили, что наше дерево имеет постоянную структуру, где каждый узел имеет свойство name (строка, которую мы будем выводить) и свойство children (массив узлов).
Итак, наша функция должна получить узел и вывести его имя, затем, поскольку все дочерние элементы похожи, мы можем один раз пройтись по массиву children и просто вызвать ту же функцию, передав дочерний элемент.
Функция printNodeNames решает нашу первоначальную задачу:
- Она начинает с вывода имени текущего узла (который передаётся в качестве аргумента).
- Затем она проходит по массиву children текущего узла и для каждого дочернего узла вызывает саму себя (рекурсия), передавая дочерний узел в качестве нового аргумента.
- Этот процесс продолжается до тех пор, пока не будут выведены все имена узлов в дереве.
Эта функция демонстрирует распространённый шаблон обхода древовидной структуры: обработка текущего узла (в данном случае вывод его имени), затем рекурсивная обработка всех дочерних узлов.
Этот метод известен как обход в глубину, поскольку он уходит как можно глубже в дерево, прежде чем вернуться назад.
Почему стоит использовать рекурсию?
Если вы ещё не убеждены в использовании рекурсивных функций, вот четыре причины, почему они так полезны:
- Простота: рекурсия часто более понятна, чем её итеративные аналоги (for, while и т. д.). Она может превратить сложные задачи в более простые.
- Решение задач: некоторые задачи по своей природе рекурсивны, например, обход деревьев, «Ханойская башня» и т. д. Для таких задач проще использовать рекурсивную функцию.
- Разделяй и властвуй: рекурсивные функции позволяют разбить большие задачи на более мелкие, управляемые подзадачи. Это основа многих эффективных алгоритмов, таких как сортировка слиянием и быстрая сортировка.
- Меньше кода: рекурсивные функции могут привести к меньшему объёму кода. Хотя более короткий код не всегда означает лучший, он может сделать код более читаемым.
Рекурсия — это не только элегантное решение некоторых проблем, но и мощный и полезный инструмент для задач, которые можно разбить на более мелкие, таких как обход дерева или сортировка списка.
Ключевые компоненты — базовый случай (условие, при котором функция прекращает вызывать саму себя) и рекурсивный случай (часть функции, которая вызывает саму себя).
Однако они могут быть сложнее для понимания и отладки, чем итеративные решения, и также могут привести к проблемам с производительностью, таким как переполнение стека, если не реализованы должным образом. Поэтому важно использовать рекурсию разумно и убедиться, что базовый случай всегда достижим.
Оригинал статьи читайте по ссылке