Реализовать функцию javascript с использованием хвостовой рекурсии - PullRequest
Новая
       22

Реализовать функцию javascript с использованием хвостовой рекурсии

2 голосов
/ 08 мая 2019

У меня есть плоский массив, представляющий дерево, и я хочу построить вложенный объект, используя хвостовую рекурсию.

У меня есть следующий код для запуска и генерации желаемого результата, но я не уверен, что это правильная реализация хвостовой рекурсии.

Пожалуйста, совет:) 

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

Ответы [ 4 ]

1 голос
/ 08 мая 2019

Вы можете оптимизировать код, уменьшив временную сложность вашего кода, сгруппировав элементы (parent_id) в объекте только один раз и извлекая его всякий раз, когда вам нужны дочерние элементы для этогоparent вместо поиска (поиска или фильтрации) через него в каждой рекурсии. 

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');
1 голос
/ 08 мая 2019

«Хвостовой вызов» - это вызов функции, который происходит как последний элемент в другой функции (в частности, любые возвращаемые значения передаются вызывающей стороне).

Например: 

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 ({
    ...

т.е. ваша функция возвращает новый объект, а не результат вызова другой функции (не говоря уже о вызове самой себе).

1 голос
/ 08 мая 2019

Основы хвостовой рекурсии - возвращать ту же функцию с измененными параметрами. Это позволяет заменить последнюю запись в стеке новым вызовом функции без увеличения размера стека.

Следующий подход использует 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; }
1 голос
/ 08 мая 2019

Ваша функция не имеет хвостового вызова и не будет при всех обстоятельствах, потому что вы вызываете рекурсивный вызов более одного раза: Помните, что оптимизация хвостового вызова в основном означает, что функция превращается в цикл, ... который невозможно в этом случае.

Тем не менее, вместо того, чтобы рекурсивно находить все вложенные элементы и многократно повторять массив, используйте id для объекта Map, тогда вам просто нужно выполнить итерацию дважды: один раз для построения карты и второй раз связать каждый элемент с его родителем. Отличную реализацию этого можно найти здесь .

Здесь была бы версия с хвостовым вызовом (я бы просто использовал цикл здесь): 

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