如何写递归，项目之间相互依赖？

Question

我想写一个函数，返回一个人所依赖的人的列表。 但是，被依赖的人，可以反过来依赖这个人自己。 例如，我想写一个函数，返回一个人所依赖的人的列表。

const people = {
    'james': {
        reliesOn: [
            'gemma',
            'jessica'
        ]
    },
    jessica: {
        reliesOn: [
            'gemma',
            'peter'
        ]
    },
    peter: {
        reliesOn: [
            'james',
            'gemma',
            'jessica',
            'ivon',
            'jamie'
        ]
    },
    jamie: {
        reliesOn: [
            'ivon'
        ]
    }
}

我试图得到以下结果： 以最简单的代码:

James relies on: gemma, jessica, peter, ivon, jamie.

杰西卡依靠：Gemma，Peter，James，Ivon，Jamie。

彼得依靠：詹姆斯，杰玛，杰西卡，伊万，杰米。

Jamie依靠：Ivon

如果已经有人问过这个问题，我表示歉意。 我从现实世界中简化了这个例子，所以我希望它是有意义的。

Answer 1

如果你真的想用 reduce 那么。

const getReliedOn = (people, name) =>
    [...(people[name]?.reliesOn || []).reduce(function recur(acc, name) {
        return acc.has(name) ? acc 
            :  (people[name]?.reliesOn || []).reduce(recur, acc.add(name));
    }, new Set([name]))].slice(1);

// Sample input
const people = {'james': { reliesOn: ['gemma','jessica']}, jessica: {reliesOn: ['gemma','peter']}, peter: {reliesOn: ['james','gemma','jessica','ivon','jamie']}, jamie: { reliesOn: ['ivon']}};
// Produce output for each person:
for (let name in people) console.log(name, "=>", ...getReliedOn(people, name));

不含备选方案 reduce，不需要递归

这是一种广度优先搜索（BFS）。它依赖于这样一个事实：当你在一个集合上迭代时，在迭代过程中你向该集合添加了值，循环也会在以后的迭代中访问这些添加的值。所以集的作用就像BFS的典型队列。

function getReliedOn(people, name) {
    let names = new Set([name]); // a set with only one entry
    for (let name of names) { // this set will extend while we loop
         if (!people[name]) continue;
         for (let other of people[name].reliesOn) names.add(other);
    }
    // get normal array from set, without original name
    return Array.from(names).slice(1);
}

// Sample input
const people = {'james': { reliesOn: ['gemma','jessica']}, jessica: {reliesOn: ['gemma','peter']}, peter: {reliesOn: ['james','gemma','jessica','ivon','jamie']}, jamie: { reliesOn: ['ivon']}};
// Produce output for each person:
for (let name in people) console.log(name, "=>", ...getReliedOn(people, name));

Answer 2

我发现在递归的时候，传递一个 "备忘录 "对象是很有用的，它可以跟踪我们已经去过的地方，以避免循环回路。

function *getDependenciesRecursive(people, person, alreadyVisited = new Set()) {
  if (alreadyVisited.has(person)) {
    return;
  }
  alreadyVisited.add(person);

  if (!(person in people)) {
    return;
  }

  for (const dependency of people[person].reliesOn) {
    yield dependency;
    yield* getDependenciesRecursive(people, dependency, alreadyVisited);
  }
}

本质上，在这样的方法中 Set 告诉我们要跳过什么。

const reliances = Object
  .entries(people)
  .reduce((results, [person, { reliesOn }]) => Object.assign(results, {
    [person]: [...getDependenciesRecursive(people, person)]
  }), {})