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

Not really, just a helper so it reads better :) - Children.Count > 0 — The_Butcher, Jan 27 '11 at 08:54

score 35 · Accepted Answer · edited Jan 26 '22 at 08:09

35

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

edited Jan 26 '22 at 08:09

Duncan Smart

31,172
10
68
70

answered Jan 27 '11 at 08:48

Jon Skeet

1,421,763
867
9,128
9,194

Isn't the number of iterators generated a function of the total number of nodes rather than of the tree depth? (DescendantsAndSelf is called for each node). – Amnon Jan 27 '11 at 08:56
If you repeatedly call DescendantsAndSelf() will it enumerate through the whole tree again or does LINQ keep the result? – The_Butcher Jan 27 '11 at 08:59
@The_Butcher: LINQ doesn't do anything magical here. It's not going to cache anything for you. Of course, you could call ToList to generate a cached copy yourself. – Jon Skeet Jan 27 '11 at 09:12
@Amnon: True, the number of iterators generated is based on the number of nodes - but the number of iterators each item needs to pass through while it's being propagated to the top iterator depends on the depth of the tree. So a deep tree will still be less efficient to iterate over than a shallow one. Will edit to make that clearer. – Jon Skeet Jan 27 '11 at 09:13
I was about to ask a new question about recursive linq and that answer(the `DescendantsAndSelf` trick) is great.(combined with SelectMany). thanks. Can this be written as Extension method ? – Royi Namir Jan 13 '14 at 07:46
@RoyiNamir: Potentially - so long as everything it needs is accessible. – Jon Skeet Jan 13 '14 at 09:29

score 5 · Answer 2 · answered Sep 16 '15 at 17:08

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

Maybe it should be clearer if you implemented the function using a Queue instead of a List. The `var c = q[0]; q.RemoveAt(0);` is really a potentially more inefficient implementation of the `Queue.Dequeue()` method — mortb, Oct 21 '15 at 11:12

score 3 · Answer 3 · answered Jan 27 '11 at 08:58

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

answered Jan 27 '11 at 08:58

Bonshington

3,970
2
25
20

1

thanks - similar to http://mutable.net/blog/archive/2008/05/23/using-linq-to-objects-for-recursion.aspx – The_Butcher Jan 27 '11 at 08:59

score 2 · Answer 4 · answered Aug 31 '17 at 01:24

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

With `.Count()` (enumerable) as opposed to `.Count` (list), you still have to go through the list each time. If you can't avoid that, you might get better performance from `.Any()` https://stackoverflow.com/questions/5741617/listt-any-or-count — codeMonkey, Jul 26 '19 at 15:29

score 1 · Answer 5 · answered Jan 27 '11 at 08:49

1

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.

answered Jan 27 '11 at 08:49

Jens

25,229
9
75
117

LINQ recursion function?

5 Answers5

Linked

Related