Приходилось ли вам когда-нибудь работать с рекурсивными алгоритмами? Я думаю приходилось. Для этого мы создаем рекурсивный метод, в котором описываем нужную логику и сам рекурсивный вызов. Однако, достаточно часто все что необходимо сделать – это обработать “плоский” список. Давайте рассмотрим как это сделать при помощи LINQ to Objects.

Итак, представим, что у нас есть определенная сущность, которая содержит список дочерних узлов аналогичного типа:

class Data
{
    public string Name { get; set; }
    public IEnumerable<Data> Childs { get; set; }
}

Мы не будем рассматривать процесс инстанциации дерева, просто предположим у нас получилась вот такая структура:

• Node1
  • Node2
    • Node3
  • Node4
    • Node5
    • Node6
  • Node7
    • Node8
  • Node9
    • Node10
      • Node11
      • Node12
        • Node13
  • Node14

Предположим, что для обработки всех этих данных нам нужен всего лишь “плоский” список этих узлов:

• Node1
• Node2
• Node3
• Node4
• Node5
• Node6
• Node7
• Node8
• Node9
• Node10
• Node11
• Node12
• Node13
• Node14

Что мы можем сделать? Можно написать стандартный рекурсивный обработчик:

public IEnumerable<Data> GetAllNodes(IEnumerable<Data> data)
{
    var result = new List<Data>();

    if (data != null)
    {
        foreach (var item in data)
        {
            result.Add(item);
            result.AddRange(GetAllNodes(item.Childs);
        }
    }

    return result;
}

Тем не менее, было бы неплохо иметь возможность с помощью LINQ to Objects обработать коллекцию рекурсивно и получить “плоский” список. Если не считать SelectMany (который здесь совсем не подходит), из стандартных возможностей LINQ нет ничего подходящего. Однако, благодаря C# 3.0 мы всегда можем расширить функциональность с помощью extension-методов. Для нашего случая напишем несложный метод расширения:

internal static class RecursiveExtension
{
    public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> recursiveFunc)
    {
        if (source != null)
        {
            foreach (var mainItem in source)
            {
                yield return mainItem;

                IEnumerable<T> recursiveSequence = (recursiveFunc(mainItem) ?? new T[] { }).SelectRecursive(recursiveFunc);

                if (recursiveSequence != null)
                {
                    foreach (var recursiveItem in recursiveSequence)
                    {
                        yield return recursiveItem;
                    }
                }
            }
        }
    }
}

Все готово. Теперь, используя этот метод расширения мы можем построить запрос для получения “плоского” списка:

IEnumerable<Data> data = ...;

// "Плоский список"
var flatList = data.SelectRecursive(c => c.Childs);

foreach(var item in flatList)
{
    Console.WriteLine(item.Name);
}
/*  Result:
    --
    Node1
    Node2
    Node3
    Node4
    Node5
    Node6
    Node7
    Node8
    Node9
    Node11
    Node12
    Node13
    Node14
*/

// Запрос
var query = from d in data.SelectRecursive(c => c.Childs)
            where d.Name.Contains("5")
            select d.Name;

foreach(var item in query)
{
    Console.WriteLine(item);
}

/*  Result:
    --
    Node5
*/