使用尾递归实现 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

你的函数没有尾调用而且在任何情况下都不会，因为你多次调用递归调用：记住尾调用优化基本上意味着函数变成了循环，.. . 这对于这种情况是不可能的。

也就是说，与其递归地查找所有嵌套元素并在数组上迭代很多次，不如使用一个 id 对象映射，然后你只需要迭代两次：一次构建映射，一次第二次 link 每个元素到它的父元素。可以找到一个很好的实现 here.

这是一个 tail-call 版本（虽然我只是在这里使用循环）：

 function listToTree([el, ...rest], parent = new Map, roots = []) {
   if(el.parentID)
      parent.get(el.parentID).children.push(el);
   else roots.push(el);

   parent.set(el.id, el);
   el.children = [];

   if(!rest.length) return roots;

   return listToTree(rest, parent, roots); // A proper tail call: This can be turned into a loop
 }

Answer 2

A "tail call" 是对一个函数的调用，它作为另一个函数中的最后一件事发生（特别是，任何 return 值都会转发给调用者）。

例如：

function foo() {
    ...
    return bar("hi");  // a tail call to bar
}

尾递归意味着它是对函数本身的尾调用，即递归尾调用：

function foo() {
    ...
    return foo();  // a recursive tail call, or: tail recursion
}

这不适用于您的代码，因为您有

function makeNestedTreeFromArray(array, id, children) {
  ...
  return ({
    ...

即您的函数 return 是一个新对象，而不是另一个函数调用的结果（更不用说对自身的调用了）。

Answer 3

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

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

该算法仅访问每个项目并构建具有多个根的树。最后只有想要的根是 returned。这种方法适用于未排序的数据，因为对于每个节点，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; }

Answer 4

您可以优化代码，方法是将项目 (parent_id) 分组到一个对象一次，并在您需要该父对象的子对象时检索它，而不是在每次递归中搜索（查找或过滤）它。

var listTree = (array, parentId, searchObj)=>{
  if(searchObj === undefined) {
      // Create the searchObject only once. Reducing time complexity of the code
      searchObj = {};
      array.forEach(data => {
        if(searchObj[data.parent]){
          searchObj[data.parent].push(data)
        }else {
          searchObj[data.parent] = [data];
        }
      });
   }
   let children = searchObj[parentId];
   // return empty array if no parent is retrieved.
   return !children ? [] : children.map(single=>{
      // Pass in the same searchObj so the the search filter is not repeated again
      single.children = listTree(array, single.id, searchObj)
      return single;
   })
}

// Run the code
listTree(myArray, 'root');

使用尾递归实现 javascript 函数

Implement javascript function using tail recursion

javascript

recursion

tail-recursion