Перед тем, как переходить к принципу решения задач с интригующим названием «Разделяй и властвуй», давайте познакомимся с концепцией, которая лежит в его основе — рекурсией.

Чтобы понять, что такое рекурсия, посмотрим на довольно распространённую задачу из фронтенда — распарсить текст из HTML-документа. Например, у нас есть вот такой вот текст:

<p>
  <b>Ребята в соцсетях иногда спрашивают, почему <em>Кекса</em> так мало</b>, где его страница в <i>«Вконтакте»</i>, и как бы видеть его почаще? Мы всё это читали, а потом у нас в офисе случилась <strong>обычная рабочая пятница</strong> — и теперь Кекса можно использовать как запрещённый <i>(и завораживающий)</i> приём в любой переписке.
</p>

А мы из него хотим получить просто

Ребята в соцсетях иногда спрашивают, почему Кекса так мало, где его страница в «Вконтакте», и как бы видеть его почаще? Мы всё это читали, а потом у нас в офисе случилась обычная рабочая пятница — и теперь Кекса можно использовать как запрещённый (и завораживающий) приём в любой переписке.

Как бы это сделать максимально изящно, да так, чтобы без регулярных выражений? Тут нам на помощь приходит уже составленный для нас DOM, который нужно просто обойти, осталось только правильно это сделать. Перед тем, как начнём писать код, давайте пройдёмся по алгоритму и исполним его «в голове» — это полезный подход, который сэкономит наше время.

Сразу же в начале нашего парсинга мы упираемся в элемент p, который не является просто текстом. Попробуем распарсить то, что у него внутри. Тут сразу же упираемся в элемент b и сразу идём парсить его «внутренности». Натыкаемся на обычный текст, который мы и искали! Пока что просто где-нибудь запишем его и продолжим парсинг. Сразу за текстом идёт em, и мы уже знаем, что нужно залезть внутрь него и распарсить его содержимое. Там только текст, поэтому допишем его в результат. Про себя отметим, что с парсингом em мы закончили, и продолжим парсить b. Находим текст, следующий за em, кладём его в результат и натыкаемся на окончание элемента b, внутри которого мы находились. Ура, что-то мы уже получили!

Так и продолжим продвигаться по тексту, мысленно начиная парсинг каждого вложенного тега рекурсивно, то есть начиная парсинг внутри парсинга. Рекурсия — это, по сути, и есть вызов функции внутри вызова этой же самой функции. В нашем примере решение свелось к тому, что мы смотрели на все данные нам элементы (в случае «захода внутрь p» это b + текст + i + текст + strong + текст + i + текст). Если это текст, то просто добавляли его в возвращаемый результат. А если это другой элемент, то запускали там точно такой же процесс парсинга, и только когда он завершится, добавляли его к результату.

Важный момент при написании рекурсивных функций (функций, которые вызывают сами себя) — это определение момента, когда функция перестанет вызывать саму себя (иначе мы просто уйдём в бесконечный цикл вызовов и никогда не остановимся). То есть базового случая. В нашем примере базовый случай — это нахождение нами текста, ведь это уже есть ответ на наш вопрос — какой текст содержится в HTML. Только этот самый HTML состоит исключительно из текста. А вот когда мы встречаем не текст — имеем рекурсивный случай. То есть случай возникновения рекурсии — вызова функцией самой себя. Важно, что каждый рекурсивный случай должен приближать нас к базовому, иначе мы так и будем проходить по одним и тем же данным и никогда не решим задачу. А сама рекурсия как раз и заключается в том, что благодаря ей мы от сложных задач переходим к всё более и более простым, пока не найдём решение каждой конкретной маленькой частицы задачи.

Если перекладывать наше словесное решение в псевдокод (он не работает, просто помогает понять, что происходит), то он будет выглядеть вот так:

function parseHtml(elements) {
  let result = ''; // Сюда будем складывать результат

  for (const element of elements) {
    if (isText(element)) { // Если внутри лежит просто текст...
      result += element // ...то кладём его в результат
    } else { // а иначе...
      result += parseHtml(element) // ...рекурсивно вызываем парсинг
    }
  }

  return result;
}