Шаг 1

Есть ещё один способ замены рекурсии, который, в отличие от циклов, не даёт особого выигрыша по памяти — применение стека (или иногда очереди). Порой можно встретить подобные алгоритмы на практике, если их разработчик не дошёл до использования рекурсии, либо просто как альтернативное решение с другой логикой. Хорошим примером альтернативности решений является обход деревьев, о котором мы узнали пару модулей назад: можно использовать либо рекурсивный поиск в глубину, либо поиск в ширину с очередью. Но также можно написать и поиск в глубину с использованием стека.

const root = document.body;
const resultElement = document.getElementById('result');

function traverse(node) {
  const result = [];

  // в рекурсивной функции...
  function recursive(node) {
    // ... сначала обрабатываем ноду, в которой находимся ...
    result.push(node.localName);

    // ...а потом вызываем её же на всех детях
    for (const child of node.children) {
      recursive(child);
    }
  }

  recursive(node);

  resultElement.innerHTML = result.join(' -> ');
}

traverse(root);

Шаг 2

Для этого мы просто берём наш поиск в ширину с очередью.

const root = document.body;
const resultElement = document.getElementById('result');

function traverse(node) {
  const result = [];

  // очередь для просмотра нод
  const queue = [];

  // куда мы сразу же кладем ноду, с которой будем начинать обход
  queue.push(node);

  // обходим, пока в очереди что-то есть
  while(queue.length) {
    // получаем ноду из списка
    const currentNode = queue.shift();

    // делаем всё, что нужно с нашей нодой (сейчас это просто перекладывание ноды в список просмотренных)
    result.push(currentNode.localName);

    // и кладем в очередь всех потомков нашей ноды.
    // из-за того, что мы будем класть потомков в конец и доставать из начала, мы гарантированно просмотрим все ноды текущего уровня перед спуском на следующий
    queue.push(...currentNode.children);
  }

  resultElement.innerHTML = result.join(' -> ');
}

traverse(root);

Шаг 3

И меняем очередь на стек! Опять же, решение с рекурсией гораздо нагляднее. Оно короче и понятнее, чем использование стека. Да и по памяти решение со стеком не выигрывает. Однако, во-первых, рекурсия может перестать вас устраивать в условиях «высокого» дерева. А во-вторых, просто забавно посмотреть, как алгоритмы получаются друг из друга и при небольших отличиях начинают работать оптимальнее с разными наборами данных.

const root = document.body;
const resultElement = document.getElementById('result');

function traverse(node) {
  const result = [];

  // очередь для просмотра нод
  const queue = [];

  // куда мы сразу же кладем ноду, с которой будем начинать обход
  queue.push(node);

  // обходим, пока в стеке что-то есть
  while(queue.length) {
    // получаем ноду из стека
    const currentNode = queue.pop();

    // делаем всё, что нужно с нашей нодой (сейчас это просто перекладывание ноды в список просмотренных)
    result.push(currentNode.localName);

    // и кладем в очередь всех потомков нашей ноды.
    // из-за того, что мы будем класть потомков в конец и доставать из начала, мы гарантированно просмотрим все ноды текущего уровня перед спуском на следующий
    queue.push(...currentNode.children);
  }

  resultElement.innerHTML = result.join(' -> ');
}

traverse(root);