# LINQ and recursive functions

• ### Question

• Hello all,

I'm blocked with a LINQ query
I have the following class :

public class MyClass
{
public MyClass(int val)
{
this.Val = val;
}

public int Val;
public List<MyClass> MyList = new List<MyClass>();
}

static void Main(string[] args)
{
MyClass c1 = new MyClass(10);
MyClass c2 = new MyClass(20);
}

I want to be able to extract the sum of the "Val" property of c1 : ie c1.Val + the value of all classes in MyList.
In this case, it's simple, I juste do
return c1.Val
+ c1.MyList.Sum(c => c.Val);

Now let's add recursion :

static void Main(string[] args)
{
MyClass c1 = new MyClass(10);
MyClass c2 = new MyClass(20);
MyClass c3 = new MyClass(20);
}

(Of course, c3 can also be linked with other classes, ...)
Here I'm a bit stuck. Which kind of query can I write to extract c1.Val + the value of all in c1.MyList + the value of all in c.MyList where c is in c1.MyList + ...

This is typically the kind of query I would write with a "WITH ... UNION ..." query in SQL but I haven't found an "equivalent" in LINQ

Any idea ?

I have seen that there was the YCombinator extension method but I'm not sure to understand correctly how it works.

Many thanks,

Monday, June 4, 2007 8:56 AM

• There has not been a recursive query operator defined yet for LINQ.  Of course, you've defined a cyclic data structure, so even if there were a recursive operator it would likely fail.

Here is a recursive traversal operator you could use.  It may have some typos.  It converts your deep hierarchy into a flat sequence.

public static class MyExtensions {

public static IEnumerable<T> Traverse(this IEnumerable<T> source, Func<T, IEnumerable<T>> fnRecurse) {

foreach(T item in source) {

yield return item;

IEnumerable<T> seqRecurse = fnRecurse(item);

if (seqRecurse != null) {

foreach(T itemRecurse in Traverse(seqRecurse, fnRecurse)) {

yield return itemRecurse;

}

}

}

}

To traverse all values in your collection:

List<MyClass> list = ...;

var total = list.Traverse(x => x.MyList).Sum(x => x.Val).

Tuesday, June 5, 2007 4:20 AM

### All replies

• Hi,

you can use the Union standard operator:

Code Snippet
var productFirstChars =
from p in products
select p.ProductName[0];
var customerFirstChars =
from c in customers
select c.CompanyName[0];

var uniqueFirstChars = productFirstChars.Union(customerFirstChars);

I've taken this sample from here where you can see much other samples you could be find useful.

Best,

Fabio

Monday, June 4, 2007 10:21 AM
• There has not been a recursive query operator defined yet for LINQ.  Of course, you've defined a cyclic data structure, so even if there were a recursive operator it would likely fail.

Here is a recursive traversal operator you could use.  It may have some typos.  It converts your deep hierarchy into a flat sequence.

public static class MyExtensions {

public static IEnumerable<T> Traverse(this IEnumerable<T> source, Func<T, IEnumerable<T>> fnRecurse) {

foreach(T item in source) {

yield return item;

IEnumerable<T> seqRecurse = fnRecurse(item);

if (seqRecurse != null) {

foreach(T itemRecurse in Traverse(seqRecurse, fnRecurse)) {

yield return itemRecurse;

}

}

}

}

To traverse all values in your collection:

List<MyClass> list = ...;

var total = list.Traverse(x => x.MyList).Sum(x => x.Val).

Tuesday, June 5, 2007 4:20 AM
• I had to use Traverse<T> to get this to compile:

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> fnRecurse)
Wednesday, December 3, 2008 11:03 PM
• Thanks for that pretty extension.
Is it possible that, this extension dont destroy the data struct of the model?

If i make something like that:

```            var x = from c in MyClass.MyList.Traverse(c=>c.MyList)

where c.Val== 1

select c;

```

The result would put in one list. So i got a List with all MyClass object which are equal to Val = 1. Thats good. But better would be if he dont destroy the model of the object.

If i got this list

List<MyClass>
+MyClass
++Val = 1
++MyList
++-MyClass
++-Val =1
++-MyList ...

and i use this Extension the result should look like above. I hope I described my problem well. If not please tell me.

greetings
http://get.lima-city.de
Sunday, April 19, 2009 7:41 AM
• Be careful, this code can cause stack overflow exceptions if you have cyclical references in your collections. Any ideas on how to update it to prevent that as an extension method?
Tuesday, December 1, 2009 8:07 AM
• It would have to track (with references, possibly WeakReferences) all previously-yielded objects and prevent itself from recursing into them. At that point, I'd be more afraid of memory use. And with that in mind, a simple yield won't be good enough and you're back in the realm of a full IEnumerator<T> implementation that doesn't return something that has already been returned.
Tuesday, April 23, 2013 12:29 AM
• I am unable to access this method.

list.Traverse is not appearing.

Am I missing something.

Tuesday, September 10, 2013 10:16 AM