Рекурсия и как она работает
В разработке сайтов много интересных задач. И сегодня хочу рассказать как провести обход DOM дерева. Постараюсь на пальцах объяснить как это работает и на примерах кода покажу что при этом происходит.
Часто ли вы встречались с ситуацией, когда нужно пройтись по DOM дереву, например, что-то найти или посчитать на странице? Думаю, такая ситуация иногда возникает. Первое, что приходит на ум — использовать рекурсивную функцию, которая выполнит требуемую операцию. Давайте подробнее разберем, что для этого требуется и как избежать неприятностей при данном способе.
Смоделируем ситуацию на каком-то конкретном примере, для этого перед собой поставим такую задачу:Требуется пройтись по DOM дереву и посчитать все вложенные элементы.
Далее нам нужна функция подсчета элементов:
Она основана на особенности замыкания сохранять значения переменной в своей области видимости. В данном случае она считает все теги, которые к ней пришли и формирует объект, где ключами выступают названия тегов. Этой функцией мы воспользуемся ниже.
Инициализируем счетчик:
Далее нам нужна функция обхода дочерних элементов конкретного HTML элемента:
Данная функция собирает массив из дочерних элементов, передает на каждой итерации название тега в нашу функцию count() и затем, если тег имеет вложенные элементы запускает рекурсию для этого элемента.
Давайте посмотрим как обрабатывает JS интерпретатор данный код. Посмотрим в каком порядке будет подсчитываться каждый элемент.
Всё выглядит хорошо. Например, наша функция обходит HTML документ из примера выше в среднем за 0.7 ms, но как обычно бывает, есть маленький нюанс.
А он заключается в Call stack— стеке вызовов, таком механизме, который позволяет интерпретатору JavaScript отслеживать в каком месте кода сейчас происходит выполнение скрипта, и в каком порядке будут выполняться те или иные функции. Так вот Call stack имеет ограничение — это лимит количества вызовов.
Посмотрим как он работает, Call stack использует принцип LIFO (Last in, First out). Возьмем вот такой пример:
А теперь визуализируем, как интерпретатор будет складывать в стек вызовы каждой функции:
Как видите, хорошо видно, что в случае с вложенными функциями стек быстро заполняется, т.е. если использовать рекурсию, то шанс получить ошибку увеличивается прилично. А если вложенных элементов будет очень много, то можно достигнуть лимита быстро.
Пусть этот лимит достаточно большой, но он всё же есть, поэтому вероятность падения приложения из-за переполнения стека вызовов сохраняется. Как мы можем нивелировать данные ограничения браузеров?
Есть несколько способов обойти ограничение, все они сводятся к использованию асинхронных операций, более подробно можно посмотреть здесь.
Понравилась статья? Больше полезного материала у меня на канале:
Итак
Рекурсивный обход DOM дерева — один самых быстрых способ получить нужный результат поставленной задачи. Следует использовать его с оглядкой на возможность переполнения стека вызовов. Подобный рекурсивный подход подходит для обхода не только DOM, но и любых сходных структур: JSON, XML и т.п.
Ссылки:
Подпишитесь на мой канал в Telegram: