Recursion with higher order functions

Question

I would like to understand the following example so it is crystal clear for me. Unfortunately, my head hangs on the line: .forEach (c => (node [c.id] = makeTree (categories, c.id))). can someone give me a hint?

let categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' }
];

let makeTree = (categories, parent) => {
  let node = {};
  categories
    .filter(c => c.parent == parent)
    .forEach(c => (node[c.id] = makeTree(categories, c.id)));
  return node;
};

console.log(makeTree(categories, null));

expected:

{
  animals: {
    mammals: {
      dogs: {
        chihuahua: null
        labrador: null
      },
      cats: {
        persian: null
        siamese: null
      }
    }
  }
}

Answer 1

Recursion is just a fancy dressed loop.

What makes recursion hard to understand is that part of the loop is hidden from you.

The hidden part is called call stack. Understand call stack and you understand recursion.

function makeTree(categories, parent) {
  let node = {};
  const stack = [{ parent, node }];
  while (stack.length) {
    const { parent, node } = stack.pop();
    for (const category of categories) {
      if (category.parent === parent) {
        const subnode = {};
        node[category.id] = subnode;
        stack.push({
          parent: category.id,
          node: subnode
        });
      }
    }
  }
  return node;
}

let categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' }
];

document.body.innerHTML = `<pre>${JSON.stringify(makeTree(categories, null), null, 2)}</pre>`

A little lengthier but exactly the way how recursion works:

function makeTree(categories, parent) {
  const stack = [{ parent }];
  let subnode; // the return value
  call: while (stack.length) {
    let { parent, node, i, c } = stack.pop();
    if (!node) {
      node = {};
      i = 0;
    } else {
      node[c.id] = subnode;
    }
    for (; i < categories.length; i++) {
      const category = categories[i];
      if (category.parent === parent) {
        stack.push({
          parent,
          node,
          i: i+1,
          c: category
        });
        stack.push({
          parent: category.id
        });
        continue call;
      }
    }
    subnode = node;
  }
  return subnode;
}

Answer 2

Does this make more sense?

Fiddle proof: https://jsfiddle.net/gz6uyodw/2/

function makeTree(categories, parent) {
  let node = {};
  const filteredArr = categories.filter(c => c.parent === parent);
  console.log('level arr', filteredArr)
  for (let obj of filteredArr) {
    const nodeToAppend = makeTree(categories, obj.id);
    console.log('node to append:', nodeToAppend)
    node[obj.id] = nodeToAppend;
  }
  return node;
}

console.log(makeTree(categories, null));

Basicaly, you are preparing a filtered array which you are preparing a level for, for the first level you have animals which contain a second filteredArr level which are mamals, mamals have groups which are dogs and there will be 2 objects in the array (added an extra one to have different filteredArr for cats and dogs) for them and so on.

Answer 3

The code can equivalently (and, imho, cleaner) be written with a normal loop and a conditional instead of filter and forEach:

function makeTree(categories, parent) {
  let node = {};
  for (const c of categories)
    if (c.parent == parent)
      node[c.id] = makeTree(categories, c.id);
  return node;
}

Now it's just an ordinary recursive function, nothing higher-order left.

Also, regarding the forEach callback specifically, that uses a totally unnecessary grouping parenthesis in the shorthand arrow function syntax instead of properly writing it with a block body (since nothing needs to be returned from a forEach callback):

.forEach(c => {
  node[c.id] = makeTree(categories, c.id);
});