Is it possible to write a recursive IEnumerable<T>

Question

I have a class like:

class Spline
    int ChildrenCount;
    Spline GetChild (int index)

class SplineCollection : IEnumerable<Spline>
    Spline Master

Is it possible to write a recursive IEnumerable for the SplineCollection where it will return all the children one by one?

EDIT: So Master is the root Box, and the hierarchy of its children can be any depth.

EDIT: By using the name Box, I think I confused some people. It's meant to be a geometric object, not a container. So changing it to Spline.

Answer 1

Yep - see this section for Recursive Iterations using C# iterators.

Answer 2

This will do a depth-first traversal of the Box 'tree'. You can then just call this method on the Master box to return all the recursive children.

public class Box
{
    // ...

    public IEnumerable<Box> GetBoxes() 
    {
        yield return this;

        for (int i=0; i<box.ChildrenCount; i++)
        {
            foreach (Box child in box.GetChild(i).GetBoxes())
            {
                 yield return child;
            }
        }
    }
}

Answer 3

class Box
{
  int ChildrenCount;
  Box GetChild (int index){/* some implementation*/}
  public IEnumerable<Box> Children
  {
    get
    {
      for(int i = 0; i != ChildrenCount; ++i)
        yield return GetChild(i);
    }
  }
  public IEnumerable<Box> Descendants
  {
    get
    {
      foreach(Box child in Children)
      {
        yield return child;
        foreach(Box desc in child.Descendants)
          yield return desc;
      }
    }
  }
}

You can call this from BoxCollection, but since Box is already a collection of Boxes, I don't see what BoxCollection's purpose is here. For that matter, having Box implement IEnumerable<Box> or one of its descendants (ICollection<Box>, IList<Box>) would probably improve usefulness.

It's also possible to do it in an iterative rather than recursive manner, which sometimes has a better performance (pretty much any time that the compiler doesn't turn the recursion into interation anyway), but recursive is more readable and normally more than performant enough.

Answer 4

Sure. You don't even really need a BoxContainer, since box, by its name, exists as a container:

public class Box
{
    private List<Box> myBoxes;

    public IEnumerable<Box> GetAllBoxes()
    {
        yield return this;
        foreach (var box in myBoxes)
        {
            var enumerator = box.GetAllBoxes().GetEnumerator();
            while(enumerator.MoveNext()) 
                yield return enumerator.Current;
        }
    }
}

If Box A held Boxes B and C, box B held boxes D and E, and box C held box F, the enumerable would come out A, B, D, E, C, F.

Answer 5

Yes, but you have to enumerate the recursive result. You can't just yield return it, because the type doesn't match.

IEnumerable<int> Triangle(int n) {
    yield return n;
    if (n > 0)
        foreach (var e in Triangle(n - 1))
            yield return e;
}

Answer 6

I would go with manually maintaining a stack instead of relying on the call stack here. The reason is because a new IEnumerable<Spline> would have to be created for each Spline visited if you used the call stack by recursively calling the method that gets the descendants. That would be inefficient. You can significantly improve the traversal by using your own stack.

public IEnumerable<Spline> Descendants
{
    get
    {
        // This performs a simple iterative preorder traversal.
        var stack = new Stack<Spline>(new Spline[] { this });
        while (stack.Count > 0)
        {
            Spline current = stack.Pop();
            yield return current;
            for (int i = current.ChildrenCount - 1; i >= 0; i--)
            {
                stack.Push(current.GetChild(i));
            }
        }
    }
}