如何编写项目相互依赖的递归？

Question

我想写一个函数，returns一个人依赖的人列表。但是，靠的是人，反过来又可以靠人自己。例如：

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

我试图获得以下结果，用最简单的代码：

詹姆斯依赖：杰玛、杰西卡、彼得、艾文、杰米

杰西卡依靠：杰玛、彼得、詹姆斯、艾文、杰米

peter 依赖于：詹姆斯、杰玛、杰西卡、艾文、杰米

杰米依靠：艾文

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

Answer 1

我发现在递归时传递一个 "memo" 对象很有用，它可以跟踪我们已经去过的地方以避免循环：

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)]
  }), {})

Answer 2

如果您真的想用 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));

如何编写项目相互依赖的递归？

How to write recursion where items depend on each other?

javascript

arrays

recursion

reduce

node.js

没有`reduce`、没有递归的替代方案

如何编写项目相互依赖的递归？

How to write recursion where items depend on each other?

javascript

arrays

recursion

reduce

node.js

没有reduce、没有递归的替代方案

没有`reduce`、没有递归的替代方案