javascript - 使用尾递归实现javascript函数

Question

我有一个代表树的平面数组，我想使用尾递归构建一个嵌套对象。

我有以下代码可以运行并生成所需的输出，但我不确定它是否是尾递归的正确实现。

请指教:)

const myArray = [
  { id: 'root' },
  { id: 0, parent: 'root' },
  { id: 1, parent: 'root' },
  { id: 2, parent: 0 },
  { id: 3, parent: 1 },
  { id: 4, parent: 2 },
  { id: 5, parent: 1 },
  { id: 6, parent: 4 },
  { id: 7, parent: 0 },
  { id: 8, parent: 0 },
];


function makeNestedTreeFromArray(array, id, children) {
  if (children.length <= 0) {
    return array.find(entry => entry.id === id);
  }
  return ({
    ...array.find(entry => entry.id === id),
    children: children.map(child => makeNestedTreeFromArray(
      array,
      child.id,
      array.filter(entry => entry.parent === child.id),
    ))
  });
}

const myTree = makeNestedTreeFromArray(
  myArray,
  'root',
  myArray.filter(entry => entry.parent === 'root'),
);

console.log(myTree);

Answer 1

尾递归的基础是返回具有更改参数的相同函数。这允许在不增加堆栈大小的情况下用函数的新调用替换最后一个堆栈条目。

以下方法使用 TCO并返回函数调用并使用标准退出条件从函数顶部的递归函数返回。

该算法仅访问每个项目并构建具有多个根的树。最后只返回想要的根。这种方法适用于未排序的数据，因为对于每个节点，id 和 parent 的信息都被使用并且它们的关系被保留。

function getTree(data, root, index = 0, tree = {}) {
    var o = data[index];
    if (!o) return tree[root];
    Object.assign(tree[o.id] = tree[o.id] || {}, o);
    tree[o.parent] = tree[o.parent] || {};
    tree[o.parent].children = tree[o.parent].children || [];
    tree[o.parent].children.push(tree[o.id]);
    return getTree(data, root, index + 1, tree);
}

const
    data = [{ id: 'root' }, { id: 0, parent: 'root' }, { id: 1, parent: 'root' }, { id: 2, parent: 0 }, { id: 3, parent: 1 }, { id: 4, parent: 2 }, { id: 5, parent: 1 }, { id: 6, parent: 4 }, { id: 7, parent: 0 }, { id: 8, parent: 0 }],
    tree = getTree(data, 'root');

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }