代码之家 › 专栏 › 技术社区 › Daniel Dyson

如何使用yield break跳出递归IEnumerable<T>循环?

yield ienumerable recursion c#

4

Daniel Dyson · 技术社区 · 15 年前

除了yieldbreak语句只从当前枚举数中中断之外,我有下面的方法可以很好地工作。我明白为什么会这样,但我对如何通过递归堆栈来实现收益率分解还是一片空白。

    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 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

这是正确的结果,但是,当我逐步遍历代码时,最外层的循环继续处理前3和前4。我该如何打破这个外环?

3 回复 | 直到 15 年前

1

2

AntonyW 13 年前

如果我得到你的代码正确,我想下面的代码将解决你的问题

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;
    }

它构建在两个扩展方法(见下文)上,应该只迭代,直到满足您的target-found条件

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方法中有一个错误(它没有迭代子对象的子对象),现在已更正

2

1

corvuscorax 15 年前

我假设函数的名称是 FindChildrenById ,否则我看不到任何递归正在进行。

在这种假设下,您可以使用异常(我强烈建议您不要这样做),也可以返回一个 KeyValuePair<bool, IEnumerable<Node>> 在哪里 bool 零件将被用于信号链的早期输出。

然后,在API级别上,公开一个只返回 IEnumerable<Node> 分道扬镳 布尔

下面是一个例子,以班级为例 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; 
    }
}

3

1

leppie 15 年前

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

那对你有用吗?

更新:

如果C有尾部递归,我建议将代码转换为 CPS .

你可以用MSIL写:)