JavaScript: Need a shared array between recursions to push the results to

Question

There's an array in which there's a family tree in which there are names of people and their sex and the names of their parents(father&mother).

Now here I'm (unsuccessfully) trying to list the names of all children for a person in this family:

function allChildren(parent) {
  var children = ancestors.filter(
    function(person) {
      if (parent.sex == 'm') {
        return person.father == parent.name
      } else {
        return person.mother == parent.name
      }
    }
  )
  if (children.length == 0) {
    console.log(parent.name);
  } else {
    children.forEach(allChildren);
  }
}

Currently this is only console logging the people who have no children. The problem is, I need to push every child into an array of results but I'm using recursion, so I can't keep a results variable shared between all recursions.

(Of course I should also check that the same name has not been pushed before -assuming there are no repetitions- which is not my question and I know how to do it, my question is about getting an array of results, filled in recursion steps gradually(each recursion step can push an element in it)).

Answer 1

Here is an approach similar to the one from KarelG. It is different enough, though, to warrant its own answer.

Differences

• This one passes the ancestors as a parameter rather than keeping them as a free variable in the function. Free variables make code harder to understand and much harder to test.

• It separates out the recursive function from the public function, keeping them together in a closure. This is a less common technique now that people are using some sort of module in many places, but it can still be useful, especially on the web. That is the (() => {/* ... return some function */ })() syntax.

• It uses a Set as the recursive accumulator, to avoid duplicates.

• It ignores the gender. I can't see a reason for checking it. If the child says that the mother is so-and-so, I don't see any point to double-checking that `mother.sex === 'f'``. I could be missing something here.

• While it keeps the existing API of supplying a full person object and returning a list of names, it would be relatively easy to switch it to supplying just the names or to return a list of people. More on that below.

• I named it allDescendents as that seemed more accurate than allChildren.

Code

const allDescendents = (() => {
  const all = (family, name, children = new Set()) => {
    const kids = family.filter(p => p.father === name || p.mother === name).map(k => k.name)
    kids.forEach(kid => (children.add(kid), all(family, kid, children)))
    return children
  }
  
  return (family, person) => Array.from(all(family, person.name))
})()

const bourbons = [ // https://en.wikipedia.org/wiki/Bourbon_family_tree
  {name: 'Philip III', sex: 'm', father: 'Louis IX', mother: 'Margaret'},
  {name: 'Robert', sex: 'm', father: 'Louis IX', mother: 'Margaret'},
  {name: 'Charles', sex: 'm', father: 'Philip III', mother: '?'},
  {name: 'Louis I', sex: 'm', father: 'Robert', mother: 'Beatrice'},
  {name: 'Philip IV', sex: 'm', father: 'Charles', mother: '?'},
  {name: 'Isabella', sex: 'f', father: 'Charles', mother: '?'},
  {name: 'Peter I', sex: 'm', father: 'Louis I', mother: 'Mary'},
  {name: 'James I', sex: 'm', father: 'Louis I', mother: 'Mary'},
  {name: 'John II', sex: 'm', father: 'Philip IV', mother: '?'},
  {name: 'Peter II', sex: 'm', father: 'James I', mother: 'Jeanne'},
  {name: 'John I', sex: 'm', father: 'James I', mother: 'Jeanne'},
  {name: 'Charles V', sex: 'm', father: 'John II', mother: '?'},
  {name: 'Joanna', sex: 'f', father: 'Peter I', mother: 'Isabella'},
  {name: 'Louis II', sex: 'f', father: 'Peter I', mother: 'Isabella'},
  {name: 'James II', sex: 'm', father: 'John I', mother: 'Catherine'},
  {name: 'Louis', sex: 'm', father: 'John I', mother: 'Catherine'},
  /* .. */
]

const louis1st = bourbons[3]

console.log(allDescendents(bourbons, louis1st))

Variants

This is factored in such a way as to make serious change fairly easy. Most of these changes can also be combined.

Return a Set

It might make more sense to return a Set of values rather than an Array. Presumably you do not want this collection to include duplicates. A Set is the right data structure for that. This solution uses a Set internally, and it's trivial to make that the public interface. Just remove the call to Array.from:

-   return (family, person) => Array.from(all(family, person.name))
+   return (family, person) => all(family, person.name)

Supply a Name

Since you're returning a collection of names, perhaps it would be easier to supply a name for the input. We can do this by altering the input parameter to receive the name:

-   return (family, person) => Array.from(all(family, person.name))
+   return (family, name) => Array.from(all(family, name))

Return People

Conversely, you might prefer to return the people objects directly. A list of names is only so helpful. A list containing the full Person object might be easier to work with. This is what that would look like:

-  const all = (family, name, children = new Set()) => {
-    const kids = family.filter(p => p.father === name || p.mother === name).map(k => k.name)
+  const all = (family, person, children = new Set()) => {
+   const kids = family.filter(p => p.father === person.name || p.mother === person.name)

-  return (family, person) => Array.from(all(family, person.name))
+  return (family, person) => Array.from(all(family, person))

Avoiding Default Parameters

If the default parameters in the function bother you (red squiggles in your editor, for instance), then you can move the parameters to the exported function. I like to keep the complexity in one place, which is why I have the defaults on the recursive function, but there is a good argument for simplifying the recursive function at the expense of the public function; it does make the recursive function somewhat easier to understand.

-   const all = (family, name, children = new Set()) => {
+   const all = (family, name, children) => {

-   return (family, person) => Array.from(all(family, person.name))
+   return (family, person) => Array.from(all(family, person.name, new Set()))

Making a module

Finally, we can easily turn this into a module. If you are deploying to the browser, this will still require a build step, but it does simplify the code: Here is one version:

const all = (family, name, children = new Set()) => {
  const kids = family.filter(p => p.father === name || p.mother === name).map(k => k.name)
  kids.forEach(kid => (children.add(kid), all(family, kid, children)))
  return children
}

const allDescendents = (family, person) => Array.from(all(family, person.name))

export {allDescendents}

Answer 2

I have commented with

what is wrong with using tail-recursion? That would make your live easier...

What I have done is to write a function that does the task with a tail recursion. By using a second argument as data holder, you can pass the data array through your recursion tree. More information about tail recursion can be found in this post: What is tail recursion?

I have created a function (interactive example at bottom)

function showChildrenOf(person, children = []) {
  // ...
}

The children = [] means that an array [] is used as default argument if no argument got supplied. The concept is default parameters. So at the start of the recursion tree, you can simply call the function with showChildrenOf(person) to have an array of all of his descendants. In the function body, I am populating children if the person has children. Then I call the function again with showChildrenOf(child, children) so that the next function call happens with the child to check if he has children and a filled in array as data holder. Since I have provided an argument, the next function handling has children=[...] instead of an empty array.

const persons =
[
 {name: 'Who Am I', father: 'Dex Bob', mother: 'Alice Mania', g:'m'}
,{name: 'Mic Mac', father: 'Who Am I', mother: 'Mega Wonder', g:'m'}
,{name: 'Ani Mani', father: 'Bob Y', mother: 'Women Wonder', g:'f'}
,{name: 'Jan Jot', father: 'Who Am I', mother: 'Wunder Bra', g:'m'}
,{name: 'Kit Kat', father: 'Jan Jot', mother: 'Unknown', g:'m'}
,{name: 'Tiny Bell', father: 'Kit Kat', mother: 'Unknown', g:'f'}
,{name: 'Bill Kid', father: 'Kit Kat', mother: 'Unknown', g:'m'}
,{name: 'Billy Wuz', father: 'Oreos Oo', mother: 'Tiny Bell', g:'m'}
];

function showChildrenOf(person, children = []) {
  const tmp = persons.filter(p => (person.g === 'm' ? person.name === p.father : person.name === p.mother));
  if (tmp.length) {
    // has children
    children.push(...tmp);
    tmp.forEach(child => showChildrenOf(child, children));
  }
  else {
    // does not have children: do nothing
  }
  return children;
}

console.log(showChildrenOf(persons[0])); // showing 'Who Am I' children
console.log(showChildrenOf(persons[1])); // showing 'Mic Mac' children

Answer 3

Here is one short way to do it (if you can use arrow function and array destructuring, but you get the idea anyway) :

function allChildren(parent) {
    const children = ancestors.filter((person) => 
        (parent.sex === 'm' && person.father === parent.name) || (parent.sex === 'f' && person.mother === parent.name));
    return [
        parent, 
        ...children.reduce((grandChildren, child) => 
            [...grandChildren, ...allChildren(child)], [])
   ];
}

Answer 4

Here's the solution I've come up with myself that works fine. It uses a recursive function and also makes use of the concept of closure in JavaScript.

So I've wrapped the recursive logic, I'd mentioned in my question earlier, in a separate inner function(which is named "all" -quickly and badly named, I know-) inside the main function(which is named "allChildren"):

function allChildren(parent) {
    var firstParentName = parent.name;
    var allChildrenArray = [];

    function all(parent) {
        var children = ancestors.filter(
            function(person) {
                if (parent.sex == 'm') {
                    return person.father == parent.name
                } else {
                    return person.mother == parent.name
                }
            }
        )
        if (children.length == 0) {
            if (allChildrenArray.indexOf(parent.name) == -1 &&
                parent.name != firstParentName) {
                allChildrenArray.push(parent.name);
            }
            return allChildrenArray;
        } else {
            children.map(function(child) {
                if (allChildrenArray.indexOf(child.name) == -1) {
                    allChildrenArray.push(child.name);
                }
            });
            children.forEach(all);
            return allChildrenArray;
        }
    }

    return all(parent);
}

Although, indeed, this is a useless function in reality. This was just a personal curiosity that I was interested in and I did it as an exercise to learn more about recursions. It's obviously a very common thing for a full-name to repeat in generations of a family tree.

Finally, calling this function using the data provided here, like this:

  console.log(allChildren(byName['Pauwels van Haverbeke'])); //byName is just a simple map from names to objects of the family tree. I haven't put the definition for the sake of brevity.

successfully gives this result:

(24) ["Lieven van Haverbeke", "Pieter Haverbeke", "Lieven Haverbeke", "Willem Haverbeke", "Daniel Haverbeke", "Jan Haverbeke", "Pieter Bernard Haverbeke", "Angela Haverbeke", "Jan Francies Haverbeke", "Pieter Antone Haverbeke", "Carel Haverbeke", "Carolus Haverbeke", "Emile Haverbeke", "Philibert Haverbeke", "Maria Haverbeke", "Livina Haverbeke", "Bernardus de Causmaecker", "Petronella de Decker", "Joanna de Causmaecker", "Maria van Brussel", "Elisabeth Haverbeke", "Laurentia Haverbeke", "Jacobus Bernardus van Brussel", "Jan Frans van Brussel"]

Answer 5

Now with a scoped function

function allChildren(parent) {
  var getChildrenRecursive = function(parent, elements){
    var children = ancestors.filter(
      function(person) {
        if (parent.sex == 'm') {
          return person.father == parent.name
        } else {
          return person.mother == parent.name
        }
      }
    )
    if (children.length == 0) {
      console.log(parent.name);
    } else {
      elements = elements.concat(children);
      children.forEach(function(child){elements = elements.concat(getChildrenRecursive(child, elements));})
      return elements;
    }
  };

  return getChildrenRecursive(parent, []);
}