具有高阶函数的递归

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) {

  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;

}