To provide the most convenient and flexible interface to your clients, write it as a class that implements Iterator<E>.
This means that the client can loop through the items found during the recursion, but they don't have to implement their "for each" code as a callback (Java doesn't have a pretty way to do that), and they can even "pause" the operation and continue it later, outside of the scope in which they began it (or abandon it at any point).
It's the trickiest to implement though. If the data structure you're traversing is a tree-like structure with parent pointers in each node then you need no other data than the current node. To get to the next node, look for a first child. If there is one, that's the next node. Otherwise try the next sibling. If there isn't one, get the parent and try to get its next sibling, and so on until you hit a null in which case there are no more items.
As a quick and dirty example, here's a treenode-like class, breaking all the rules about encapsulation to save some space here:
class SimpleNode
{
String name;
public SimpleNode parent, firstChild, nextSibling;
public SimpleNode(String n) { name = n; }
public void add(SimpleNode c)
{
c.parent = this;
c.nextSibling = firstChild;
firstChild = c;
}
public String getIndent()
{
StringBuffer i = new StringBuffer();
for (SimpleNode n = this; n != null; n = n.parent)
i.append(" ");
return i.toString();
}
}
Now let's create a tree from it:
SimpleNode root = new SimpleNode("root");
SimpleNode fruit = new SimpleNode("fruit");
root.add(fruit);
fruit.add(new SimpleNode("pear"));
fruit.add(new SimpleNode("banana"));
fruit.add(new SimpleNode("apple"));
SimpleNode companies = new SimpleNode("companies");
root.add(companies);
companies.add(new SimpleNode("apple"));
companies.add(new SimpleNode("sun"));
companies.add(new SimpleNode("microsoft"));
SimpleNode colours = new SimpleNode("colours");
root.add(colours);
colours.add(new SimpleNode("orange"));
colours.add(new SimpleNode("red"));
colours.add(new SimpleNode("blue"));
Now, to spell this out for anyone new to this idea, what we want to be able to do is this:
for (final SimpleNode n : new SimpleNodeIterator(root))
System.out.println(n.getIndent() + "- " + n.name);
And get this (I've made the above code generate something that looks like a hierarchical bullet list in SO):
To do this, we have to map some standard operations onto our SimpleNode class:
class SimpleNodeIterator extends TreeIterator<SimpleNode>
{
public SimpleNodeIterator(SimpleNode root)
{ super(root); }
protected SimpleNode getFirstChild(SimpleNode of)
{ return of.firstChild; }
protected SimpleNode getNextSibling(SimpleNode of)
{ return of.nextSibling; }
protected SimpleNode getParent(SimpleNode of)
{ return of.parent; }
}
And finally, at the bottom of our design, TreeIterator<TNode> is a very reusable abstract base class that does the rest, now we've told it how to navigate our node class:
abstract class TreeIterator<TNode> implements Iterator<TNode>,
Iterable<TNode>
{
private TNode _next;
protected TreeIterator(TNode root)
{ _next = root; }
public Iterator<TNode> iterator()
{ return this; }
public void remove()
{ throw new UnsupportedOperationException(); }
public boolean hasNext()
{ return (_next != null); }
public TNode next()
{
if (_next == null)
throw new NoSuchElementException();
TNode current = _next;
_next = getFirstChild(current);
for (TNode ancestor = current;
(ancestor != null) && (_next == null);
ancestor = getParent(ancestor))
{
_next = getNextSibling(ancestor);
}
return current;
}
protected abstract TNode getFirstChild(TNode of);
protected abstract TNode getNextSibling(TNode of);
protected abstract TNode getParent(TNode of);
}
(It's mildly naughty in that it implements Iterator<E> and Iterable<E> on the same object. This just means that you have to new up a fresh object in order to iterate a second time; don't try to reuse the same object).
This means that if your hierarchical structure consists of nodes for which you can define those three simple navigational operations, then all you have to do is derive your own equivalent of SimpleNodeIterator. This makes it very easy to enable this capability on any tree implementation.
If what you're iterating doesn't have a way to get the parent, you need to keep a stack during the iteration. Each time you descend a level, you push the state for the current level onto the stack. When you finish iterating at the current level, you pop the last state off the stack and continue with it. When the stack is empty, you're done. This means you have some intermediate storage, but its maximum size is proportional to the depth of the recursion rather than the number of items, so assuming the data is roughly balanced then it should be a lot more storage-efficient than copying all the items to a list before you return it.