LINQ recursion function?

Question

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

public class SomeItem 
{
     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;
    }

Answer 1

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

Answer 2

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();

Answer 3

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