Recursive method: single element parameter or collection of elements?

Question

I have a question about the merits of two different approaches to implementing a recursive method. I've always followed the approach of version 1, i.e., accepting a single Node parameter, but I recently encountered the style used in version 2, which accepts a collection of Nodes.

Consider the following Node class, along with the 2 versions of the Visit method:

class Node
{
    public List<Node> children = new List<Node>();
    // other data members 
}

Version 1 accepts a single Node parameter:

Visit(Node n)
{
  DoSomethingUsefulWith(n);

  foreach (Node child in n.children)
    Visit(child);
}

Version 2 accepts a collection of Nodes:

Visit(List<Node> nodes)
{
  foreach (Node n in nodes)
  {
    DoSomethingUsefulWith(n);
    Visit(n.children);
  }
}

Are there any benefits, even stylistically, to using one form over the other? Should the choice be based solely on whether you're starting with a single Node vs a collection of Nodes, even though it would be trivial to use either method version in either case?

Answer 1

You should pass as little as possible parameters in your recursion functions (regarding even the size of the memory dedicated to the type you use). That's the general rule I follow. If you pass some big structures you can run out of memory. If you're using reference type though, it's not an issue.

Answer 2

The only significant difference I can see is in the ease of calling.

How about this version 3:

void Visit(Node n)
{
    DoSomethingUsefulWith(n);
    Visit(n.children);
}

void Visit(List<Node> nodes)
{
    foreach (Node n in nodes)
        Visit(n);
}

Answer 3

Stylistically it depends on the root of the type of object you are recursing.

Effectively they are the same. unless my brain is in park.....

Answer 4

I wouldn't implement version 2, always version 1.
Version 2 is basically version 1 in a for-each loop

If you later on decide that you want to call the method with one parameter you can always re-use version 1.
If you only have version 2 and one node you have to create a dummy list to use version 1.

I don't think that performance is a real issue here. Both methods have one (by reference) argument, they should use about the same amount of memory.

However .NET might be able to optimize one of the two a bit better. Profile both methods to be sure.

Answer 5

I think there is no real benefit to version 2 - only that it limits your function's flexibility, since you cannot start your recursion with a single node anymore.

Imo, version 1 is way easier to read, so I would go for number I.

Answer 6

I prefer the signature that takes a single node since I don't then have to construct an artificial list if I only want to do the operation on that node and it's children. It's just as easy to use on a list of nodes as well as you merely iterate over the list and apply it to each.

Answer 7

Personally I think that version 1 better reflects the recursive definition of a tree (which is usually based on a single node). Therefore I'd favor version 1.