Рекурсивная функция JS с setTimeout

Вообще говоря, когда вы хотите выполнить итерацию в ширину, вам нужно использовать очередь (например, FIFO). Javascript не имеет собственной структуры данных очереди, поэтому он просто использует массив и shift, но по-прежнему выполняет свою работу.

Здесь вы просто кладете все в очередь на каждом уровне. Это гарантирует, что дети будут вытеснены вслед за родителями, и поэтому вы сначала перебираете родителей. Обычно с помощью графика вы также отслеживаете, где вы были, но поскольку это дерево, петель отсутствует.

var data = [ { id: "0" }, { id: "1", children: [ { id: "1.1", children: [ { id: "1.1.1", children: [ { id: "1.1.1.1", children: [ { id: "1.1.1.1.1" }, { id: "1.1.1.1.2" }, { id: "1.1.1.1.3" } ] }, { id: "1.1.1.2" }, { id: "1.1.1.3" } ] }, { id: "1.1.2" }, { id: "1.1.3" }, ] }, { id: "1.2" }, { id: "1.3" } ] }, { id: "2" }, { id: "3" } ];

function recursive(queue) {
  var current = queue.shift();
  if (current === undefined) return
  console.info(current.id)
  if (current.children) {
    current.children.forEach(node => {
      queue.push(node)
    })
  }
  setTimeout(function() {
    recursive(queue)
  })
}

recursive(data);

РЕДАКТИРОВАТЬ - ДЛЯ ГЛУБИНЫ:

Если вам сначала нужна глубина, вы в основном используете стек, а не очередь. Здесь это немного странно, потому что вы заботитесь о порядке дочерних элементов, поэтому мы загружаем стек в обратном порядке.

var data = [ { id: "0" }, { id: "1", children: [ { id: "1.1", children: [ { id: "1.1.1", children: [ { id: "1.1.1.1", children: [ { id: "1.1.1.1.1" }, { id: "1.1.1.1.2" }, { id: "1.1.1.1.3" } ] }, { id: "1.1.1.2" }, { id: "1.1.1.3" } ] }, { id: "1.1.2" }, { id: "1.1.3" }, ] }, { id: "1.2" }, { id: "1.3" } ] }, { id: "2" }, { id: "3" } ];
  
function recursive(stack) {
    let current = stack.pop()
    if (current === undefined) return
    console.info(current.id)
    if (current.children)  {
        stack.push(...current.children.reverse())
    }
    setTimeout(function(){
        recursive(stack)
    })
}
recursive(data.reverse());

Запутанные провода

Рекурсия и асинхронность - разные понятия, но нет причин, по которым мы не можем использовать их вместе. Сначала мы рассмотрим некоторые синхронные обходы, а затем добавим поддержку асинхронности по мере продвижения. Мне нравится этот стиль ответа, потому что мы можем видеть одну и ту же программу, представленную разными способами. Мы фокусируемся на изменениях небольшой, которые оказывают влияние большой.

Начнем с одного подхода с использованием генераторов -

const Empty =
  Symbol ()

const breadthFirst = function* ([ node = Empty, ...nodes ])
{
  if (node === Empty)
    return
  else
    (yield node, yield* breadthFirst (nodes.concat (node.children || [])))
}

const data =
  [{ id: "0" },{id: "1",children: [{id: "1.1",children: [{id: "1.1.1",children: [{id: "1.1.1.1",children: [{ id: "1.1.1.1.1" },{ id: "1.1.1.1.2" },{ id: "1.1.1.1.3" }]},{ id: "1.1.1.2" },{ id: "1.1.1.3" }]},{ id: "1.1.2" },{ id: "1.1.3" },]},{ id: "1.2" },{ id: "1.3" }]},{ id: "2" },{ id: "3" }]

for (const x of breadthFirst (data))
  console.info (x.id)
  
// 0 1 2 3 1.1 1.2 1.3 1.1.1 ... 1.1.1.1.3

Собрать все поля id в массив

const values =
  Array.from (breadthFirst (data), x => x.id)

console.info (values)
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

В качестве альтернативы, мы можем сделать breadthFirst функцией высшего порядка, очень похожей на Array.prototype.map или Array.prototype.reduce.

const Empty =
  Symbol ()

const breadthFirst = (f = identity, [ node = Empty, ...nodes]) =>
  node === Empty
    ? []
    : [ f (node), ...breadthFirst (f, nodes.concat (node.children || [])) ]

const data =
  [{ id: "0" },{id: "1",children: [{id: "1.1",children: [{id: "1.1.1",children: [{id: "1.1.1.1",children: [{ id: "1.1.1.1.1" },{ id: "1.1.1.1.2" },{ id: "1.1.1.1.3" }]},{ id: "1.1.1.2" },{ id: "1.1.1.3" }]},{ id: "1.1.2" },{ id: "1.1.3" },]},{ id: "1.2" },{ id: "1.3" }]},{ id: "2" },{ id: "3" }]
  
const values =
  breadthFirst (x => x.id, data)
  
console.info (values)
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Мы могли бы сделать breadthFirst асинхронной функцией, используя Promise.

const breadthFirst = (f = identity, [ node = Empty, ...nodes]) =>
  node === Empty
    ? Promise.resolve ([])
    : breadthFirst (f, nodes.concat (node.children || [])) .then (answer => [ f (node), ...answer ])

const promiseOfValues =
  breadthFirst (x => x.id, data)

promiseOfValues.then (console.info, console.error)
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Наконец, мы можем сделать асинхронную функцию f, предоставляемую пользователем.

const breadthFirst = (f = identity, [ node = Empty, ...nodes]) =>
  node === Empty
    ? Promise.resolve ([])
    : Promise.resolve (node) .then (f) .then (value =>
        breadthFirst (f, nodes.concat (node.children || [])) .then (answer =>
          [ value, ...answer ]))

const promiseOfValues =
  breadthFirst (x => new Promise (r => setTimeout (r, 250, x.id)), data)

promiseOfValues.then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Наконец, снова, лол, используйте новый синтаксис async / await

const breadthFirst = async (f = identity, [ node = Empty, ...nodes]) =>
{
  if (node === Empty)
    return []

  const value =
    await Promise.resolve (node) .then (f)

  const answer =
    await breadthFirst (f, nodes.concat (node.children || []))

  return [ value, ...answer ]
}

const promiseOfValues =
  breadthFirst (x => new Promise (r => setTimeout (r, 250, x.id)), data)

promiseOfValues.then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Будет универсальным

Рекурсия - это функциональное наследие, а функциональное программирование - это возможность многократного использования. breadthFirst берет на себя множество обязанностей. Помимо построения правильной последовательности узлов, нам нужно подумать об API-интерфейсе Promise и как, чтобы связать последовательность вместе; это бремя, и его можно снять. Ниже мы можем сделать процесс более общим, используя свертку обеспечить регресс - unfold.

const unfold = (f, init) =>
  f ( (x, next) => [ x, ...unfold (f, next) ]
    , () => []
    , init
    )

const nextLetter = c =>
  String.fromCharCode (c.charCodeAt (0) + 1)

const alphabet =
  unfold
    ( (next, done, c) =>
        c > 'z'
          ? done ()
          : next (c, nextLetter (c))
    , 'a'
    )

console.info (alphabet)
// [ a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z ]

Array.prototype.reduce принимает набор значений, а уменьшает принимает одно значение - unfold принимает одно значение, а разворачивается - набор значений.

const fib = (n = 0) =>
  unfold
    ( (next, done, [ n, a, b ]) =>
        n < 0
          ? done ()
          : next (a, [ n - 1, b, a + b ])
    , [ n, 0, 1 ]
    )

console.info (fib (20))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ]

Хорошо, но вы хотели развернуть асинхронный - просто добавьте ключевые слова async и await

const asyncUnfold = async (f, init) =>
  f ( async (x, acc) => [ x, ...await asyncUnfold (f, acc) ]
    , async () => []
    , init
    )

Давайте продемонстрируем это с помощью менее надуманной функции, такой как асинхронный getChildren. В реальной программе это может принимать узел или идентификатор узла и извлекать его из базы данных, возвращая обещание дочерних узлов. Ниже мы видим резкое снижение сложности breadthFirst. Обратите внимание, что здесь программист не обременен сложностями Promise.

const getChildren = (node) =>
  new Promise ((resolve, _) =>
    setTimeout (resolve, 250, node.children || []))

const Empty =
  Symbol ()

const breadthFirst = (nodes) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...rest, ...await getChildren (node) ])
    , nodes
    )

breadthFirst (data) .then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Как оказалось, вам не нужен обход в ширину, вам нужен в глубину. Преимущество используемых здесь подходов заключается в том, что мы можем использовать одну и ту же общую функцию unfold для различных обходов - ниже мы реализуем depthFirst, идентичный breadthFirst, но на этот раз мы вносим одно крошечное изменение.

const breadthFirst = (nodes) =>
const depthFirst = (nodes) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          // breadth-first
          next (node.id, [ ...rest, ...await getChildren (node) ])
          // depth-first
          : next (node.id, [ ...await getChildren (node), ...rest ])
    , nodes
    )

depthFirst (data) .then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', ..., '2', '3' ]

примечания

Последний комментарий о вашем data - это ошибка, которую делают многие люди при моделировании иерархических деревьев данных. В вашем объекте data каждый элемент является узлом, а каждый элемент children является узлом; однако сам data не является узлом, это просто массив. Это несоответствие является проблемой и фактически делает вашу программу менее универсальной.

Помните, что я говорил выше о фолде (reduce) и unfold? reduce берет коллекцию и выдает значение один, unfold делает наоборот. При обходе дерева мы начинаем с одиночный узел, а не с массива узлов.

const breadthFirst = (nodes) =>
const breadthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...rest, ...await getChildren (node) ])
    , nodes
    , [ node ]
    )

const depthFirst = (nodes) =>
const depthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...await getChildren (node), ...rest ])
    , nodes
    , [ node ]
    )

breadthFirst ({ id: 'root', children: data }) .then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ 'root', '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

depthFirst ({ id: 'root', children: data }) .then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ 'root', '0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', ..., '2', '3' ]

Полная демонстрация программы

const asyncUnfold = async (f, init) =>
  f ( async (x, acc) => [ x, ...await asyncUnfold (f, acc) ]
    , async () => []
    , init
    )
    
const Empty =
  Symbol ()
  
const depthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...await getChildren (node), ...rest ])
    , [ node ]
    )
    
const breadthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [...rest, ...await getChildren (node) ])
    , [ node ]
    )

const getChildren = (node) =>
  new Promise ((resolve, _) =>
    setTimeout (resolve, 250, node.children || []))

const data =
  [{ id: "0" },{id: "1",children: [{id: "1.1",children: [{id: "1.1.1",children: [{id: "1.1.1.1",children: [{ id: "1.1.1.1.1" },{ id: "1.1.1.1.2" },{ id: "1.1.1.1.3" }]},{ id: "1.1.1.2" },{ id: "1.1.1.3" }]},{ id: "1.1.2" },{ id: "1.1.3" },]},{ id: "1.2" },{ id: "1.3" }]},{ id: "2" },{ id: "3" }]

breadthFirst ({ id: 'foo', children: data }) .then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ 'foo', '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

depthFirst ({ id: 'bar', children: data }) .then (console.info, console.error)
// => Promise
// 4 seconds later ...
// [ 'bar', '0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', ..., '2', '3' ]