javascript - 带有 setTimeout 的递归 JS 函数

Question

我有以下代码

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(current) {
  var first = current[0];
  current.shift();
  var remaining = current;

  console.log(first.id);

  if (first.children) {
    setTimeout(function(){
      recursive(first.children);
    })
  }

  if (remaining.length) {
    setTimeout(function(){
      recursive (remaining);
    });
  }
}

recursive(data);

由于 setTimeout，此输出不按顺序排列



问题:

如何更改它以输出如下图所示的内容？

我怎么知道这个递归函数的最后一次迭代？列表用完后，我需要运行一些东西。

我 不能使用 forEach 因为我 有出于不同的原因使用 setTimeouts。我了解 setTimeout 在循环中无法正常工作。有任何想法吗？？？？

期望的输出:

Answer 1

缠线

递归和异步是独立的概念，但我们没有理由不能一起使用它们。首先，我们将查看一些同步遍历，然后添加对异步的支持。我喜欢这种回答方式，因为我们可以看到以多种方式表示的同一个程序。我们专注于产生巨大影响的小变化。

我们从一种使用生成器的方法开始——

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.log (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.log (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.log (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.log, 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.log, 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.log, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

通用

递归是一种功能性遗产，而功能性编程就是关于可重用性。以上 breadthFirst承担许多责任。除了构建正确的节点序列之外，我们还需要考虑 Promise API 以及如何将序列连接在一起；这是一种负担，可以解除。下面，我们可以使用反向折叠使该过程更通用 - 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.log (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.log (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 .在实际程序中，这可能会获取一个节点或节点 ID，并从返回该节点子节点的 Promise 的数据库中获取它。下面，我们看到 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.log, 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.log, 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对象，每一项都是一个Node，每一项都是 children是一个节点；但是， data它本身不是一个节点，它只是一个普通的数组。这种不一致是一个痛点，实际上使您的程序不那么通用。

记住我所说的 fold ( 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.log, 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.log, 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.log, 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.log, 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' ]