Вот подход, аналогичный подходу от KarelG. Однако он достаточно отличается, чтобы оправдать свой ответ.
Отличия
Этот параметр передает предков в качестве параметра, а не сохраняет их в качестве свободной переменной в функции. Свободные переменные усложняют понимание и тестирование кода.
Он отделяет рекурсивную функцию от публичной функции, удерживая их вместе в замыкании. Это менее распространенная техника сейчас, когда люди используют какой-то модуль во многих местах, но он все еще может быть полезен, особенно в Интернете. Это синтаксис (() => {/* ... return some function */ })().
Он использует набор в качестве рекурсивного аккумулятора, чтобы избежать дублирования.
Он игнорирует пол. Я не вижу причины для проверки. Если ребенок говорит, что мать такая-то, я не вижу смысла перепроверять этот `mother.sex === 'f'``. Я мог бы что-то здесь упустить.
Несмотря на то, что он сохраняет существующий API, предоставляющий полный объект человека и возвращающий список имен, было бы относительно легко переключить его на предоставление только имен или для возврата списка людей. Подробнее об этом ниже.
Я назвал это allDescendents, поскольку это казалось более точным, чем allChildren.
код
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))
Варианты
Это учтено таким образом, чтобы сделать серьезные изменения довольно легкими. Большинство из этих изменений также могут быть объединены.
Возврат Set
Возможно, имеет смысл возвращать Set значений, а не Array. Предположительно, вы не хотите, чтобы эта коллекция содержала дубликаты. Set - правильная структура данных для этого. Это решение использует Set внутри, и сделать его общедоступным интерфейсом тривиально. Просто уберите звонок на Array.from:
- return (family, person) => Array.from(all(family, person.name))
+ return (family, person) => all(family, person.name)
Введите имя
Поскольку вы возвращаете коллекцию имен, возможно, было бы проще указать имя для ввода. Мы можем сделать это, изменив входной параметр, чтобы получить имя:
- return (family, person) => Array.from(all(family, person.name))
+ return (family, name) => Array.from(all(family, name))
Возвращение людей
И наоборот, вы можете предпочесть возвращать объекты людей напрямую. Список имен только так полезен. С списком, содержащим полный объект Person, может быть проще работать. Вот как это будет выглядеть:
- 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))
Как избежать параметров по умолчанию
Если параметры по умолчанию в функции вас беспокоят (например, красные кривые в вашем редакторе), то вы можете переместить параметры в экспортированную функцию. Мне нравится хранить сложность в одном месте, поэтому у меня есть значения по умолчанию для рекурсивной функции, но есть хороший аргумент для упрощения рекурсивной функции за счет публичной функции; это делает рекурсивную функцию несколько проще для понимания.
- 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()))
Создание модуля
Наконец, мы можем легко превратить это в модуль. Если вы развертываете в браузере, для этого по-прежнему потребуется этап сборки, но он действительно упрощает код: Вот одна из версий:
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}