# Is this Recursion + Linq example inefficient?

I have a hierarchy of of groups, and I want to get a collection of all the lowest level groups (or leaves if we'll look at this as a tree).

I wrote the following code. Is it inefficient?

public static class FeatureWeightGroupExtensions
{
public static IEnumerable<IFeatureWeightGroup> GetLeafGroups(this IFeatureWeightGroup featureWeightGroup)
{
return GetLeafGroupsRecursive(featureWeightGroup).ToList();
}

private static IEnumerable<IFeatureWeightGroup> GetLeafGroupsRecursive(IFeatureWeightGroup featureWeightGroup)
{
if (!featureWeightGroup.ChildGroups.Any())
return Enumerable.Repeat(featureWeightGroup, 1);

return featureWeightGroup.ChildGroups.Aggregate(Enumerable.Empty<IFeatureWeightGroup>(),
(allGroups, group) =>
allGroups.Concat(GetLeafGroupsRecursive(group)));
}
}

• Wow, I kept reading it as feather weight until I realised it says feature :-D Feb 24 '11 at 15:35

return featureWeightGroup.ChildGroups.Aggregate(Enumerable.Empty<IFeatureWeightGroup>(),
(allGroups, group) =>
allGroups.Concat(GetLeafGroupsRecursive(group)));


It looks like it can be replaced with:

return featureWeightGroup.ChildGroups
.SelectMany(g => GetLeafGroupsRecursive(group));


Which probably will not be much better from performance point of view, but looks cleaner.

• Actually it would be much better performance. The Aggregate version would instantiate many Concat iterators, which would constantly forward MoveNext() calls to each other, while your improvement instantiates only one SelectMany iterator. Feb 24 '11 at 15:36

As already pointed out by Snowbear and my comment on his answer, you can improve the performance and readability by using SelectMany instead of Concat.

However, I notice that you are using ToList() at the end anyway. This pulls into question the benefit of using LINQ and all those SelectMany iterators in the first place. Using LINQ sacrifices performance at the benefit of lazy evaluation, but you are not using the lazy-evaluation aspect. Therefore, if performance is what you are after, then don’t use LINQ that much:

public static class FeatureWeightGroupExtensions
{
public static IEnumerable<IFeatureWeightGroup> GetLeafGroups(this IFeatureWeightGroup featureWeightGroup)
{
var list = new List<IFeatureWeightGroup>();
populateList(list, featureWeightGroup);
return list;
}

private static void populateList(List<IFeatureWeightGroup> list, IFeatureWeightGroup featureWeightGroup)
{
if (!featureWeightGroup.ChildGroups.Any())

This is the most performance-optimised way I can think of, while at the same time also being significantly easier to read than the original or the SelectMany alternative.