Any way to make this recursive function better/faster?

Question

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

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

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

    return result;
}

Answer 1

I'd separate iteration and adding items to a list:

public IEnumerable<Channel> ChildrenOf(Channel root)
{
    yield return root;
    foreach(var c in root.Children)
       foreach(var cc in ChildrenOf(c))
          yield return cc;
}

Answer 2

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

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;
    }
}

And now to achieve your aim, you just say:

    static List<Channel> 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.

Answer 3

Put the recursive part in a private method, so that you can add the items directly to the list instead of creating intermediate lists:

public List<Channel> ChildrenOf(Channel startingChannel) {
  List<Channel> result = new List<Channel>();
  AddChildren(startingChannel, result);
  return result;
}

private void AddChildren(Channel channel, List<Channel> list) {
  foreach (Channel child in channel.Children) {
    list.Add(child);
    AddChildren(child, list);
  }
}

(This is basically the same principle as Polity suggested, only it's implemented in two methods so that you don't have to create an empty list to call it.)

Answer 4

Share your result list would be one way of preventing allocations and esspecially collections to happen

 public List<Channel> ChildrenOf(Channel startingChannel, List<Channel> result) 
    { 
        foreach (Channel child in startingChannel.Children) 
        { 
            result.Add(child);

            // this will internally add to result
            ChildrenOf(child, result);
        } 

        return result; 
    }