如何使用yield break打破递归IEnumerable<T>循环？

Question

我有下面这个方法，它很好用，但是yield break语句只能跳出当前的枚举器。我知道为什么会这样，但是我不知道如何将yield break传递到递归堆栈中。

    private static IEnumerable<Node> FindChildrenById(IEnumerable nodes, string parentText) {
        var en = nodes.GetEnumerator();
        var targetFound = false;
        while (en.MoveNext())  {
            var node = en.Current as Node;
            if (node != null) 
            {
                if (node.Parent == null && string.IsNullOrEmpty(parentText))
                {
                    //Returns the top level nodes if an empty parentIdis entered
                    targetFound = true;
                    yield return node;
                }
                else if (node.Parent != null && node.Parent.Text == parentText)
                {
                    //returns the nodes belonging to the parent
                    yield return node;
                }
                else
                {
                    //Recurse into the children to see whether one of these is the node to find
                    foreach (var nd in FindChildrenById(node.Nodes, parentText))
                    {
                        yield return nd;
                    }
                }
            }
        }
        if (targetFound)
        {
            yield break;
        }
    }

当我有以下节点并将“Top 2 a”作为parentText传递时...

Top 1
    Top 1 a
    Top 1 b
Top 2
    Top 2 a
       Top 2 aa
       Top 2 ab
       Top 2 ac
    Top 2 b
Top 3
    Top 3 a
    Top 3 b
Top 4

...然后我得到了结果:

Top 2 aa
Top 2 ab
Top 2 ac

这是正确的结果，但当我逐步执行代码时，最外层循环继续处理 Top 3 和 Top 4。如何跳出这个外部循环？

- Daniel Dyson

Answer 1

如果我的理解是正确的，我想下面的代码将解决你的问题。

private static IEnumerable<Node> FindChildrenById(IEnumerable nodes, string parentText)
    {
        var result =
               (from node in nodes
                where (node.Parent == null && string.IsNullOrEmpty(parentText))
                      || (node.Parent != null && node.Parent.Text == parentText)
                select node).TakeWhile(node => !(node.Parent == null && string.IsNullOrEmpty(parentText)));
        return result;
    }

这是基于两个扩展方法构建的（见下文），并且只应迭代到达目标条件为止。

public static class IEnumerablExtensions
        {
            //Will iterate the graph in depth first order
            public static IEnumerable<TResult> Select<TResult>(this IEnumerable collection, Func<Node, TResult> selector)
            {
                foreach (var obj in collection)
                {
                    var node = obj as Node;
                    if (node != null)
                    {
                        yield return selector(node);
                        foreach (var n in node.Nodes.Select(selector))
                        {
                           yield return n;
                        }
                    }
                }
            }

        public static IEnumerable<Node> Where(this IEnumerable collection, Predicate<Node> pred)
        {
            foreach (var node in collection.Select(x => x)) //iterate the list in graph first order
            {
                if (pred(node))
                    yield return node;
            }
        }
    }

编辑：原帖中Select方法存在错误（它没有迭代子节点的子节点），现已更正。

- Rune FS

---

感谢 @Rune FS。我会尝试并回报。 - Daniel Dyson

Answer 2

//Returns the top level nodes if an empty parentIdis entered
targetFound = true;
yield return node;
yield break;

这个方案对你可行吗？

更新：

我再考虑了一下。这可能在递归中有些棘手。你需要保留一些状态变量来跳出所有循环。

如果C#支持尾递归，我建议将代码转换为CPS。

你总可以用MSIL编写它 :)

- leppie

---

我发誓我到处都能看到你，通常就在我即将提问/回答之前。有点吓人 :D - Rei Miyasaka

@Rei Miyasaka：并不是一直，但我确实会有一些有趣的冲动 :) - leppie

Answer 3

我假设该函数实际上被命名为FindChildrenById，否则我看不到任何递归。

在此假设下，您可以使用异常（但我强烈建议不要这样做），或者返回一个KeyValuePair<bool, IEnumerable<Node>>，其中bool部分将用于向上链路信号早期离开。

然后，在API级别上，公开一个包装器方法，它简单地返回IEnumerable<Node>部分并且丢弃了bool部分。

以下是示例，给定类Node:

public class Node
{
    List<Node> children;
    public string Text { get; set; }
    public List<Node> Children { get { return children ?? (children = new List<Node>()); } }
}

你可以像这样遍历和快捷方式：

public class NodeTraverser
{
    private static KeyValuePair<bool, IEnumerable<Node>> GetChildrenById(string text, Node node)
    {
        if(node.Text == text)
        {
            return new KeyValuePair<bool,IEnumerable<Node>>(true, node.Children);
        }
        foreach(var child in node.Children)
        {
            var result = GetChildrenById(text, child);
            if(result.Key)
            {
                return result; // early out
            }
        }
        return new KeyValuePair<bool,IEnumerable<Node>>(false, Enumerable.Empty<Node>());
    }

    public static IEnumerable<Node> FindChildrenbyId(string text, Node root)
    {
        return GetChildrenById(text, root).Value; 
    }
}

- corvuscorax

---

是的，对不起，我已经在我的代码中修复了那个小错误，但是把早期版本粘贴到了问题中。谢谢。我认为我不能返回一个KeyValuePair并仍然使用yield语句。它必须出现在返回IEnumerable<T>的方法内部。 - Daniel Dyson

我举了一个例子来解释我的意思.. yield语句并不是必需的，对吗？ - corvuscorax

是的，在这种情况下，我正在处理大量的节点，这些节点被转换和操作。通过使用yield return和yield break，我能够在找到我要查找的内容后退出循环，而无需转换或操作其余部分。您的示例要求在进行任何处理之前预加载、转换和操作整个集合。但还是谢谢。 - Daniel Dyson

抱歉，但是您为什么认为需要预加载所有内容呢？ - corvuscorax

异常的概念并不是很糟糕，它只会在找到一个值时被抛出，因此性能不会受到太大影响。这也是函数式语言中常用的非局部返回模式。请参见http://en.wikipedia.org/wiki/Continuation。 - leppie

我不喜欢在这种情况下使用异常的原因，不是因为性能考虑，而是因为我认为使用异常来表示正常条件是设计不良。它也无法与日志记录和其他依赖注入很好地配合，因为它假定整个代码库中存在某些合理的模式。 - corvuscorax