c# - 如何将 "unroll"构造成 "recursive"

Question

不确定如何调用它，但假设您有一个看起来像这样的类:

class Person
{
    public string Name;
    public IEnumerable<Person> Friends;
}

然后你有一个人，你想递归地“展开”这个结构，所以你最终得到一个没有重复的所有人的列表。

你会怎么做？我已经做了一些似乎可行的东西，但我很好奇其他人会怎么做，尤其是如果 Linq 有一些内置的东西，你可以巧妙地使用它来解决这个小问题:)

---

这是我的解决方案:

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    // Stop if subjects are null or empty
    if(subjects == null)
        yield break;

    // For each subject
    foreach(var subject in subjects)
    {
        // Yield it
        yield return subject;

        // Then yield all its decendants
        foreach (var decendant in SelectRecursive(selector(subject), selector))
            yield return decendant;
    }
}

可以这样使用:

var people = somePerson.SelectRecursive(x => x.Friends);

Answer 1

我认为 LINQ 中没有内置任何功能来执行此操作。

像这样递归地做是有问题的——你最终会创建大量的迭代器。如果树很深，这可能效率很低。 Wes Dyer和 Eric Lippert都写了关于此的博客。

您可以通过删除直接递归来消除这种低效率。例如:

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects,
    Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
    {
        yield break;
    }

    Queue<T> stillToProcess = new Queue<T>(subjects);

    while (stillToProcess.Count > 0)
    {
        T item = stillToProcess.Dequeue();
        yield return item;
        foreach (T child in selector(item))
        {
            stillToProcess.Enqueue(child);
        }
    }
}

这也会改变迭代顺序——它变成广度优先而不是深度优先；重写它仍然是深度优先是很棘手的。我还将其更改为不使用 Any() - 这个修订版不会多次评估任何序列，这在某些情况下会很方便。请注意，这确实有一个问题 - 由于排队，它会占用更多内存。我们可能可以通过存储迭代器队列而不是项目来缓解这种情况，但我不确定……它肯定会更复杂。

有一点需要注意(我在查找博客文章时 ChrisW 也注意到了 :) - 如果您的 friend 列表中有任何循环(即如果 A 有 B，并且 B 有 A)那么您将永远递归.