HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMajor

Any way to make this recursive function better/faster?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thisanymakewayfunctionbetterfasterrecursive

Problem

Is there anything that can be done differently for this function? Any way to make it faster?

public List ChildrenOf(Channel startingChannel)
{
    List result = new List();

    foreach (Channel child in startingChannel.Children)
    {
        result.Add(child);
        result.AddRange(ChildrenOf(child));
    }

    return result;
}

Solution

Just to round out the other answers: I would be inclined to write your solution like this:

static IEnumerable DepthFirstTreeTraversal(T root, Func> children)      
{
    var stack = new Stack();
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        // If you don't care about maintaining child order then remove the Reverse.
        foreach(var child in children(current).Reverse())
            stack.Push(child);
        yield return current;
    }
}


And now to achieve your aim, you just say:

static List AllChildren(Channel start)
    {
        return DepthFirstTreeTraversal(start, c=>c.Children).ToList();
    }


Now you have a more general-purpose tool that you can use to get a depth-first traversal of any tree structure, not just your particular structure.

Another nice feature of my solution is that it uses a fixed amount of call stack space. Even if your hierarchy is twenty thousand deep, you never run out of stack space because the method is not recursive to begin with. All the information that would be needed for recursion is stored on the "stack" data structure instead of in activation records on the real call stack.

Code Snippets

static IEnumerable<T> DepthFirstTreeTraversal<T>(T root, Func<T, IEnumerable<T>> children)      
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        // If you don't care about maintaining child order then remove the Reverse.
        foreach(var child in children(current).Reverse())
            stack.Push(child);
        yield return current;
    }
}
static List<Channel> AllChildren(Channel start)
    {
        return DepthFirstTreeTraversal(start, c=>c.Children).ToList();
    }

Context

StackExchange Code Review Q#5648, answer score: 41

Revisions (0)

No revisions yet.