使用尾递归实现javascript函数 [英] Implement javascript function using tail recursion

问题描述

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

I have got a flat array representing a tree, and I want to build a nested object using tail recursion.

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

I've got the following code to run and generate the desired output, but I am not sure if it is a proper implementation of tail recursion.

请指教:)

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

推荐答案

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

The basics of a tail recursion is to return the same function with changed parameters. This allows to replace the last stack entry with the new call of the function without increasing the stack size.

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

The following approach uses a TCO and returns the function call and uses a standard exit condition to return from a recursive function at the top of the function.

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

The algorithm visits each item only ones and builds a tree which has multiple roots. At the end only the wanted root is returned. This approach works for unsorted data, because for every node, both information of id and parent are used and their relation is preserved.

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; }

这篇关于使用尾递归实现javascript函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！