LINQ recursion function?

Let's take this n-tier deep structure for example:

public class So开发者_高级运维meItem 
{
     public Guid ID { get;set; }
     public string Name { get; set; }
     public bool HasChildren { get;set; }
     public IEnumerable<SomeItem> Children { get; set; }
}

If I am looking to get a particular Item by ID (anywhere in the structure) is there some LINQ goodness I can use to easily get it in a single statement or do I have to use some recursive function as below:

   private SomeItem GetSomeItem(IEnumerable<SomeItem> items, Guid ID)
    {
        foreach (var item in items)
        {
            if (item.ID == ID)
            {
                return item;
            }
            else if (item.HasChildren)
            {
                return GetSomeItem(item.Children, ID);
            }
        }
        return null;
    }

---

LINQ doesn't really "do" recursion nicely. Your solution seems appropriate - although I'm not sure HasChildren is really required... why not just use an empty list for an item with no children?

An alternative is to write a DescendantsAndSelf method which will return all of the descendants (including the item itself), something like this;

// Warning: potentially expensive!
public IEnumerable<SomeItem> DescendantsAndSelf()
{
    yield return this;
    foreach (var item in Children.SelectMany(x => x.DescendantsAndSelf()))
    {
        yield return item;
    }
}

However, if the tree is deep that ends up being very inefficient because each item needs to "pass through" all the iterators of its ancestry. Wes Dyer has blogged about this, showing a more efficient implementation.

Anyway, if you have a method like this (however it's implemented) you can just use a normal "where" clause to find an item (or First/FirstOrDefault etc).

---

Here's one without recursion. This avoids the cost of passing through several layers of iterators, so I think it's about as efficient as they come.

    public static IEnumerable<T> IterateTree<T>(this T root, Func<T, IEnumerable<T>> childrenF)
    {
        var q = new List<T>() { root };
        while (q.Any())
        {
            var c = q[0];
            q.RemoveAt(0);
            q.AddRange(childrenF(c) ?? Enumerable.Empty<T>());
            yield return c;
        }
    }

Invoke like so:

            var subtree = root.IterateTree(x => x. Children).ToList();

---

hope this helps

public static IEnumerable<Control> GetAllChildControls(this Control parent)
{
  foreach (Control child in parent.Controls)
  {
    yield return child;

    if (child.HasChildren)
    {
      foreach (Control grandChild in child.GetAllChildControls())
        yield return grandChild;
    }
  }
}

---

It is important to remember you don't need to do everything with LINQ, or default to recursion. There are interesting options when you use data structures. The following is a simple flattening function in case anyone is interested.

    public static IEnumerable<SomeItem> Flatten(IEnumerable<SomeItem> items)
    {
        if (items == null || items.Count() == 0) return new List<SomeItem>();

        var result = new List<SomeItem>();
        var q = new Queue<SomeItem>(collection: items);

        while (q.Count > 0)
        {
            var item = q.Dequeue();
            result.Add(item);

            if (item?.Children?.Count() > 0)
                foreach (var child in item.Children)
                    q.Enqueue(child);
        }

        return result;
    }

---

While there are extension methods that enable recursion in LINQ (and probably look like your function), none are provided out of the box.

Examples of these extension methods can be found here or here.

I'd say your function is fine.