patterncsharpMajor
Any way to make this recursive function better/faster?
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:
And now to achieve your aim, you just say:
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.
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.