Hoje eu ia implementar um método para atravessar um gráfico arbitrariamente profundo e achatá-lo em um único enumerável. Em vez disso, eu fiz uma pequena pesquisa primeiro e achei isso:

<code>public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector)
{
    foreach (T item in enumerable)
    {
        yield return item;

        IEnumerable<T> seqRecurse = recursivePropertySelector(item);

        if (seqRecurse == null) continue;
        foreach (T itemRecurse in Traverse(seqRecurse, recursivePropertySelector))
        {
            yield return itemRecurse;
        }
    }
}
</code>

Em teoria, isso parece bom, mas, na prática, descobri que ele tem um desempenho significativamente pior do que usar código escrito à mão equivalente (conforme surge a situação) para passar por um gráfico e fazer o que for necessário. Eu suspeito que isso é porque neste método, para cada item que ele retorna, a pilha tem que desanuviar em algum nível arbitrariamente profundo.

Eu também suspeito que esse método funcionaria de forma muito mais eficiente se a recursão fosse eliminada. Eu também não sou muito bom em eliminar a recursão.

Alguém sabe como reescrever esse método para eliminar a recursão?

Obrigado por qualquer ajuda.

EDIT: Muito obrigado por todas as respostas detalhadas. Eu tentei benchmarking a solução original vs solução de Eric vs não usando um método de enumerador e em vez disso atravessando recursivamente com um lambda e, estranhamente, a recursão de lambda é significativamente mais rápida do que qualquer um dos outros dois métodos.

<code>class Node
{
    public List<Node> ChildNodes { get; set; } 

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

class Foo
{
    public static void Main(String[] args) 
    {
        var nodes = new List<Node>();
        for(int i = 0; i < 100; i++)
        {
            var nodeA = new Node();
            nodes.Add(nodeA);
            for (int j = 0; j < 100; j++)
            {
                var nodeB = new Node();
                nodeA.ChildNodes.Add(nodeB);
                for (int k = 0; k < 100; k++)
                {
                    var nodeC = new Node();
                    nodeB.ChildNodes.Add(nodeC);
                    for(int l = 0; l < 12; l++)
                    {
                        var nodeD = new Node();
                        nodeC.ChildNodes.Add(nodeD);
                    }
                }
            }
        }            

        nodes.TraverseOld(node => node.ChildNodes).ToList();
        nodes.TraverseNew(node => node.ChildNodes).ToList();

        var watch = Stopwatch.StartNew();
        nodes.TraverseOld(node => node.ChildNodes).ToList();
        watch.Stop();
        var recursiveTraversalTime = watch.ElapsedMilliseconds;
        watch.Restart();
        nodes.TraverseNew(node => node.ChildNodes).ToList();
        watch.Stop();
        var noRecursionTraversalTime = watch.ElapsedMilliseconds;

        Action<Node> visitNode = null;
        visitNode = node =>
        {
            foreach (var child in node.ChildNodes)
                visitNode(child);
        };

        watch.Restart();
        foreach(var node in nodes)
            visitNode(node);
        watch.Stop();
        var lambdaRecursionTime = watch.ElapsedMilliseconds;
    }
}
</code>

Onde TraverseOld é o método original, TraverseNew é o método de Eric, e obviamente o lambda é o lambda.

Na minha máquina, TraverseOld leva 10127 ms, TraverseNew leva 3038 ms, a recursão de lambda leva 1181 ms.

Isso é típico que métodos de enumerador (com retorno de rendimento) podem levar 3X contanto que a execução imediata? Ou alguma outra coisa está acontecendo aqui?