具有高阶函数的递归

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

      }

    }

  }

}

Answer 1

代码可以等效地（并且，恕我直言，更干净）用普通循环和条件而不是filterand编写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);});

Answer 2

递归只是一个花哨的循环。使递归难以理解的是循环的一部分对您隐藏。隐藏的部分称为调用栈。了解调用堆栈，您就了解递归。function makeTree(categories, parent) {&nbsp; let node = {};&nbsp; const stack = [{ parent, node }];&nbsp; while (stack.length) {&nbsp; &nbsp; const { parent, node } = stack.pop();&nbsp; &nbsp; for (const category of categories) {&nbsp; &nbsp; &nbsp; if (category.parent === parent) {&nbsp; &nbsp; &nbsp; &nbsp; const subnode = {};&nbsp; &nbsp; &nbsp; &nbsp; node[category.id] = subnode;&nbsp; &nbsp; &nbsp; &nbsp; stack.push({&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parent: category.id,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node: subnode&nbsp; &nbsp; &nbsp; &nbsp; });&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; }&nbsp; return node;}let categories = [&nbsp; { id: 'animals', parent: null },&nbsp; { id: 'mammals', parent: 'animals' },&nbsp; { id: 'cats', parent: 'mammals' },&nbsp; { id: 'dogs', parent: 'mammals' },&nbsp; { id: 'chihuahua', parent: 'dogs' },&nbsp; { id: 'labrador', parent: 'dogs' },&nbsp; { id: 'persian', parent: 'cats' },&nbsp; { id: 'siamese', parent: 'cats' }];document.body.innerHTML = `<pre>${JSON.stringify(makeTree(categories, null), null, 2)}</pre>`有点长，但正是递归的工作方式：function makeTree(categories, parent) {&nbsp; const stack = [{ parent }];&nbsp; let subnode; // the return value&nbsp; call: while (stack.length) {&nbsp; &nbsp; let { parent, node, i, c } = stack.pop();&nbsp; &nbsp; if (!node) {&nbsp; &nbsp; &nbsp; node = {};&nbsp; &nbsp; &nbsp; i = 0;&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; node[c.id] = subnode;&nbsp; &nbsp; }&nbsp; &nbsp; for (; i < categories.length; i++) {&nbsp; &nbsp; &nbsp; const category = categories[i];&nbsp; &nbsp; &nbsp; if (category.parent === parent) {&nbsp; &nbsp; &nbsp; &nbsp; stack.push({&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parent,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i: i+1,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c: category&nbsp; &nbsp; &nbsp; &nbsp; });&nbsp; &nbsp; &nbsp; &nbsp; stack.push({&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parent: category.id&nbsp; &nbsp; &nbsp; &nbsp; });&nbsp; &nbsp; &nbsp; &nbsp; continue call;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; subnode = node;&nbsp; }&nbsp; return subnode;}