Implement javascript function using tail recursion

Question

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.

Please advice :)

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

no, it's not and btw it's a very bad algo with a lot of iterations for finding childrens. for having a tail recursion, you need to return the last expression by taking the function itselft, not between or inside some objects. — Nina Scholz, May 08 '19 at 08:34
check this SO answer which I think is the best possible solution as far as complexity & recursion is concerned (it assumes the list is sorted though) - https://stackoverflow.com/a/18018037/2332159 — planet_hunter, May 08 '19 at 08:44

Jonas Wilms · Answer 1 · 2019-05-08T08:57:04.523

Your function does not have a tail call and it won't under all circumstances, because you call the recursive call more than once: Remember that tail call optimization basically means that the function is turned into a loop, ... which is impossible for this case.

That said, instead of finding all the nested elements recursively and iterating over the array a lot of times, use a id to object Map, then you just need to iterate twice: Once to build up the Map, and a second time to link each element to it's parent. A great implementation of that can be found here.

Here would be a tail-call version (I would just use a loop here though):

 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
 }

score 1 · Answer 2 · answered May 08 '19 at 08:57

A "tail call" is a call to a function that occurs as the last thing in another function (in particular, any return values are forwarded to the caller).

For example:

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

Tail recursion means it's a tail call to the function itself, i.e. a recursive tail call:

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

This does not apply to your code because you have

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

I.e. your function returns a new object, not the result of another function call (let alone a call to itself).

Nina Scholz · Accepted Answer · 2019-05-08T10:47:46.900

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.

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.

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

Mzndako · Answer 4 · 2019-05-08T09:34:28.697

You can optimize the code by reducing the time complexity of your code by grouping the items (parent_id) in an object just once and retrieving it whenever you need the children for that parent instead of searching (find or filter) through it in every recursion.

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

Implement javascript function using tail recursion

4 Answers4

Linked