Recursive Iteration

9/10/2004 4:15:58 AM

Recursive Iteration

I know the title sounds like an oxymoron; that's why I chose it. The C# 2.0 spec used to have an example of recursive iterators witn binary trees, but now I don't see it anymore. It's pretty trivial to write, but I'll use the example from GrantRi's post. Brad Abrams created his own recursive iterator to enumerate files in subdirectories.

public class BinaryTree<DataType> {
    public DataType Data;
    public BinaryTree LeftChild;
    public BinaryTree RightChild;

    public IEnumerable<DataType> InOrder {
        get {
            if (LeftChild != null)
                foreach (DataType d in LeftChild.InOrder)
                    yield return d;
            yield return Data;
            if (RightChild != null)

                foreach (DataType d in RightChild.InOrder)
                    yield return d;
        }
    }
}

I have to admit that this is a pretty readable way to write an enumerator, but Grant is troubled by the N additional objects allocated by an iterator over that of a non-iterative implementation. So, he proceeds to create an iterative (sic) iterator using a temporary stack.

Grant claims that his stack-based iterator performs faster because it doesn't allocate any memory. Though I do agree that his stack-based solution is faster, I don't necessarily buy the reasoning he used. Temporary allocations are fast enough that you should always measure.

There's another problem with recursive iteration of a binary tree. The recursive iterator and the stack-based iterator have different time complexity. The stack-based iterator runs in linear time, while the recursive iterator runs in time n log(n), which is actually not that bad, but suboptimal.

Consider this. To retrieve an element eight levels deep in the binary tree, the cost of that next call to MoveNext in the top-level recursive iterator will include the cost of calling MoveNext on the seven nested iterators. That single call to MoveNext is multiplied eight times.

An alternative to using a stack-based iterator to achieve linear-time performance is to create a public method that iterates over the items, calling a passed-in anonymous method for each one. This approach uses less memory than with iterators, and likely executes faster.

public class BinaryTree<DataType> {
    public DataType Data;
    public BinaryTree LeftChild;
    public BinaryTree RightChild;

    public void Foreach(Action<DataType> action)
   
{
            if (LeftChild != null)
                LeftChild.Foreach(action);
            action(Data);
            if (RightChild != null)

                RightChild.Foreach(action);
    }
}

Then you can write the following foreach like construction.

tree.Foreach(delegate
    {
          // Perform actions
    });

Comments

 

Navigation

Categories

About

Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media