# Recursion in collections count?

• ### Question

• I have a collection like so

Parents.Child

ChildIsParent.FirstGrandChild

and so on...

my question is how would i return a count of total items i have in a recursive tree??? pass a method a collection it returns me and int of the total collection count.

Give youself a round of applause!!
Tuesday, May 3, 2011 8:29 PM

• That is the most performance oriented way to do it.  However, if you need a method which does this without deriving a new collection:

```public int TotalNodeCount(NodeCollection collection)
{
int ret = collection.Count;

foreach(Node node in collection)
{
ret += TotalNodeCount(node.Children);
}

return ret;

}
```
• Proposed as answer by Wednesday, May 11, 2011 7:10 AM
• Marked as answer by Thursday, May 12, 2011 1:48 AM
• Unmarked as answer by Friday, May 13, 2011 4:49 AM
• Marked as answer by Tuesday, May 17, 2011 1:19 AM
Wednesday, May 4, 2011 5:07 PM

### All replies

• If all of the elements in the tree are of the same type, e.g., Node, which has a collection called Children, then you can use this method:

``` public static IEnumerable<T> Visit<T>(this T baseObject, Func<T, IEnumerable<T>> visitFunction, Func<T, bool> stopCondition = null)
{
if (baseObject == null)
{
throw new ArgumentNullException("baseObject");
}
if (visitFunction == null)
{
throw new ArgumentNullException("visitFunction");
}
if (stopCondition == null || !stopCondition(baseObject))
{
var children = visitFunction(baseObject);
foreach (var child in children)
{
yield return child;
var grandchildren = child.Visit(visitFunction, stopCondition);
foreach (var grandchild in grandchildren)
{
yield return grandchild;
}
}
}
}```

The usage would be like this:

```class Node
{
public IEnumerable<Node> Children { get; }
}
List<Node> nodes = new List<Node>();
var allDescendents = from node in nodes select node.Visit(n=>n.Children).SelectMany(list=>list);
var count = allDescendents.Count();```
HTH,

Evan

Tuesday, May 3, 2011 8:46 PM
• Hi,

It is interresting to implement it with Visitor pattern, But it is very simple with Aggregate method :

```using System.Collections.Generic;
using System.Linq;

namespace RecursiveCount
{
public class Asset
{
public int Id { get; set; }
public List<Asset> Parents { get; set; }
public List<Asset> Children { get; set; }

public Asset(int id)
{
this.Id = id;
this.Parents = new List<Asset>();
this.Children = new List<Asset>();
}

}

class Program
{
static void Main(string[] args)
{
Asset oAsset1 = new Asset(1);
Asset oAsset2 = new Asset(2);
Asset oAsset3 = new Asset(3);
Asset oAsset4 = new Asset(4);
Asset oAsset5 = new Asset(5);

// get all children count of oAsset1
int count = RecursiveChildrenCount(oAsset1);

}

static int RecursiveChildrenCount(Asset oAsset)
{
if (oAsset.Children.Count == 0)
{
return 0;
}
else
{
return oAsset.Children.Count + oAsset.Children.Aggregate(0,
(count, asset) => count += RecursiveChildrenCount(asset));
}

}
}
}

```
Regards,

aelassas.free.fr
Tuesday, May 3, 2011 10:17 PM
• Hello,

Why do you need to iterate your tree to get that info ? this kind of data should be managed by you in each parent.

The moment you add a new child to a parent, the add method should request the amount of items for this collection similarly the remove method should discount it.

That way the total amount of items is always stored progressively.

Eyal (http://shilony.net), Regards.

Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.

Tuesday, May 3, 2011 11:10 PM
• Right Seems like I should be able to write a class that is derived from ArrayList oir List<MyObject> and it has a total property and evertime i call the add method I increment the count???? is that the correct thinking to have Eyal?
Give youself a round of applause!!
Wednesday, May 4, 2011 4:03 PM
• That is the most performance oriented way to do it.  However, if you need a method which does this without deriving a new collection:

```public int TotalNodeCount(NodeCollection collection)
{
int ret = collection.Count;

foreach(Node node in collection)
{
ret += TotalNodeCount(node.Children);
}

return ret;

}
```
• Proposed as answer by Wednesday, May 11, 2011 7:10 AM
• Marked as answer by Thursday, May 12, 2011 1:48 AM
• Unmarked as answer by Friday, May 13, 2011 4:49 AM
• Marked as answer by Tuesday, May 17, 2011 1:19 AM
Wednesday, May 4, 2011 5:07 PM
• Right Seems like I should be able to write a class that is derived from ArrayList oir List<MyObject> and it has a total property and evertime i call the add method I increment the count???? is that the correct thinking to have Eyal?

Sorry, but I can't figure whether you are sarcastic or really want an answer, I'll go and assume the latter.

You can't just go and increment it, you need to check whether the child is already in the collection and whether it is changed.

You need to notify the root of changes whenever the amount of elements for a certain child got changed, so certainly there should be some tracking mechanism.

Regardless to my recommendation, recursions are the easiest to implement however they don't scale as good as you expect for complex trees, therefor I thought like giving you an alternative, that's all, take it or leave it.

I think that these kind of things should be done moderately, I don't know whether it should scale or not, or how large it is, again I assume.

Eyal (http://shilony.net), Regards.

Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.

Thursday, May 5, 2011 1:33 AM
• I couldn't help my self leaving a comment on the three ways of doing recursive counting in nested collections presented in the posts. Especially when you read the second sentance of Eyal's signature - "Good programmers write code that humans can understand".

Evan, very interesting method, but do you really think that someone who asks how to do recursive counting in the first place will know what's going on in this pattern, not to mention the use of 4.0 framework features in your sample. Besides, the amount of IL this produces isn't justified.

My vote goes to CS001's solution. Simple, effective and human readable.

/Calle

- Still confused, but on a higher level -
Thursday, May 5, 2011 8:29 AM
• Hi,

You do not need to create any class because It already exists :ObservableCollection<T> Class

CollectionChanged gets fired when an item is added, removed, changed, moved, or the entire list is refreshed. You can subscribe to CollectionChanged to receive notifications.

Kind regards,

aelassas.free.fr
Thursday, May 5, 2011 9:49 AM
• Here is an example I made using recursions, once I'll have the time I'll implement the approach I've posted in my previous post.

```namespace Experimental.Console.Tree
{
using System.Collections.Generic;

internal interface IRoot<T> : IEnumerable<T>
{
int Count { get; }

bool Remove(INode<T> node);

int GetTotalElements();
}
}

namespace Experimental.Console.Tree
{
using System.Collections.Generic;

internal interface INode<T> : IEnumerable<T>
{
int Count { get; }

IList<IRoot<T>> Roots { get; }

bool HasChildren { get; }

bool Remove(T element);
}
}

namespace Experimental.Console.Tree
{
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

internal class Root : IRoot<object>
{

public Root()
{
_nodes = new List<INode<object>>();
}

#region Implementation of IRoot<object>

public int Count
{
get { return _nodes.Count; }
}

{
}

public bool Remove(INode<object> branch)
{
return _nodes.Remove(branch);
}

public int GetTotalElements()
{
int totalElements = 0;

foreach (var node in _nodes)
{
if (node.HasChildren)
{
//LINQ: totalElements += node.Roots.Sum(root => root.GetTotalElements());

foreach (var root in node.Roots)
{
totalElements += root.GetTotalElements();
}
}

totalElements += node.Count;
}

}

#endregion

#region Implementation of IEnumerable

public IEnumerator<object> GetEnumerator()
{
return _nodes.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

#endregion
}
}

namespace Experimental.Console.Tree
{
using System;
using System.Collections;
using System.Collections.Generic;

internal class Node : INode<object>
{
private IList<IRoot<object>> _root;

public Node()
{
_items = new List<object>();
}

#region Implementation of INode<object>

public int Count
{
get { return _items.Count; }
}

public IList<IRoot<object>> Roots
{
get
{
return _root ?? (_root = new List<IRoot<object>>());
}
}

public bool HasChildren
{
get
{
if (_root == null)
{
return false;
}
else
{
return _root.Count > 0;
}
}
}

{
}

public bool Remove(object element)
{
return _items.Remove(element);
}

#endregion

#region Implementation of IEnumerable

public IEnumerator<object> GetEnumerator()
{
return _items.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

#endregion
}
}

namespace Experimental.Console.Tree
{
using System;

internal static class Test
{
public static void Run(params string[] args)
{
// Root

Root root = new Root();

// Root\Node

Node node = new Node
{
new object(),
new object()
}; // We could use the .Add method to add these items but the collection initializer is just more convenient (imo) and less imperative

// Root\Node\Root1

Root root1 = new Root();

// Root\Node\Root1\Node11

Node node11 = new Node
{
new object(),
new object(),
new object()
};

// Root\Node\Root1\Node12

Node node12 = new Node
{
new object(),
new object()
};

// Root\Node\Root1\Node12\Root121

Root root121 = new Root();

// Root\Node\Root1\Node12\Root121\Node1211

Node node1211 = new Node
{
new object()
};

// Print the total amount of elements.

Console.WriteLine(root.GetTotalElements());

}
}
}

```

Eyal (http://shilony.net), Regards.

Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.
Thursday, May 5, 2011 4:51 PM
• Your code would be much smaller if you use an ObservableCollection.
aelassas.free.fr
Thursday, May 5, 2011 5:10 PM
• Your code would be much smaller if you use an ObservableCollection.

Not required in this kind of scenario and I think that the amount of code is irrelevant.

Bear in mind that this is an example, reducing the amount of code only makes it worst for new comers.

However, I might use it to implement the approach I previously advised to the OP.

Eyal (http://shilony.net), Regards.

Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.
Thursday, May 5, 2011 5:26 PM
• To assume I am a new comer or a newbie or dont understand recursion  is strange just answer the questions and keep it moving please and thank you....just looking for the best way to do recursion in this sense...thanks for the help!!!! more and more opinions lead to better development and just learning more.  purpose of Forumn i thought was for collaborative thinking thats it right??? or am i wrong??
Give youself a round of applause!!
Thursday, May 12, 2011 5:30 PM
• To assume I am a new comer or a newbie or dont understand recursion  is strange just answer the questions and keep it moving please and thank you....just looking for the best way to do recursion in this sense...thanks for the help!!!! more and more opinions lead to better development and just learning more.  purpose of Forumn i thought was for collaborative thinking thats it right??? or am i wrong??

I wasn't assuming anything, I just stated that a full-blown example can/may help new comers, no one said anything about you.

Eyal (http://shilony.net), Regards.

Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.

Friday, May 13, 2011 3:00 AM
• best solution thank you so much
Monday, December 10, 2018 7:03 AM