使用高阶函数的递归

Question

我想要理解以下示例，以便我能够非常清楚地了解它。不幸的是，我的脑子卡在这一行上：.forEach (c => (node[c.id] = makeTree(categories, c.id))). 有人可以给我一个提示吗？

let categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' }
];

let makeTree = (categories, parent) => {
  let node = {};
  categories
    .filter(c => c.parent == parent)
    .forEach(c => (node[c.id] = makeTree(categories, c.id)));
  return node;
};

console.log(makeTree(categories, null));

expected:

{
  animals: {
    mammals: {
      dogs: {
        chihuahua: null
        labrador: null
      },
      cats: {
        persian: null
        siamese: null
      }
    }
  }
}

- user10358817

---

我理解了，但是在写答案时很难解释清楚。 - Kevin.a

那行代码到底有什么不清楚的？它只是在filter之后创建了一个剩余类别的子树。 - Sebastian Simon

正如Kevin所说，很难给出答案，因为代码是有效的，你只需要理解它。有时候，当代码不是ES6时，添加许多控制台日志并仔细阅读它们会更容易理解代码。https://jsfiddle.net/bcfj71ry/3/ - Karl-André Gagnon

Answer 1

这段代码可以等价地（并且在我看来更加简洁）使用普通循环和条件语句来编写，而不是使用 filter 和 forEach：

function makeTree(categories, parent) {
  let node = {};
  for (const c of categories)
    if (c.parent == parent)
      node[c.id] = makeTree(categories, c.id);
  return node;
}

现在它只是一个普通的递归函数，没有高阶函数了。

此外，关于forEach回调函数，它在简写箭头函数语法中完全不必要地使用了分组括号，而不是用块体正确地编写它（因为从forEach回调函数中不需要返回任何内容）：

.forEach(c => {
  node[c.id] = makeTree(categories, c.id);
});

- Bergi

---

作为对上一段的跟进，我个人建议仅在意图从回调函数返回某些内容时使用简写箭头语法。正如Bergi所正确解释的那样，没有返回任何东西，因此使用大括号而不是简写形式可以确认该意图。 - Patrick Roberts

Answer 2

这个有更好的理解吗？

验证程序：https://jsfiddle.net/gz6uyodw/2/

function makeTree(categories, parent) {
  let node = {};
  const filteredArr = categories.filter(c => c.parent === parent);
  console.log('level arr', filteredArr)
  for (let obj of filteredArr) {
    const nodeToAppend = makeTree(categories, obj.id);
    console.log('node to append:', nodeToAppend)
    node[obj.id] = nodeToAppend;
  }
  return node;
}

console.log(makeTree(categories, null));

基本上，您正在准备一个过滤后的数组，为其准备一个级别，对于第一级别，您有包含第二个filteredArr级别的动物，哺乳动物有分组，其中狗将有2个对象在数组中（添加了额外的一个来具有不同的过滤器用于猫和狗），等等。

- EugenSunic

Answer 3

递归只是一个穿着花哨的循环。

让递归难以理解的是，循环的一部分对你来说是隐藏的。

这个隐藏的部分被称为调用栈。了解调用栈，你就能理解递归。

function makeTree(categories, parent) {
  let node = {};
  const stack = [{ parent, node }];
  while (stack.length) {
    const { parent, node } = stack.pop();
    for (const category of categories) {
      if (category.parent === parent) {
        const subnode = {};
        node[category.id] = subnode;
        stack.push({
          parent: category.id,
          node: subnode
        });
      }
    }
  }
  return node;
}

let categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' }
];

document.body.innerHTML = `<pre>${JSON.stringify(makeTree(categories, null), null, 2)}</pre>`

稍微有点长，但这正是递归的工作方式：

function makeTree(categories, parent) {
  const stack = [{ parent }];
  let subnode; // the return value
  call: while (stack.length) {
    let { parent, node, i, c } = stack.pop();
    if (!node) {
      node = {};
      i = 0;
    } else {
      node[c.id] = subnode;
    }
    for (; i < categories.length; i++) {
      const category = categories[i];
      if (category.parent === parent) {
        stack.push({
          parent,
          node,
          i: i+1,
          c: category
        });
        stack.push({
          parent: category.id
        });
        continue call;
      }
    }
    subnode = node;
  }
  return subnode;
}

- marzelin

---

请注意，这与递归调用栈所做的不完全相同，其中多个循环在同一时间内激活 categories。此外，您的代码会在处理元素之前执行 node[category.id] = subnode; - 因为它不知道如何从递归调用中“返回”。 - Bergi

@Bergi 我在想是否有人注意到了它；很高兴知道有人深刻理解递归。我会添加另一段代码，更长但更符合递归的工作方式。 - marzelin

SCNR，以确保递归的工作原理，并区分哪个堆栈帧被继续执行 :-) - Bergi

@Bergi 很好 :-) - marzelin