To provide the most convenient and flexible interface for your clients, write it as a class that implements Iterator<E> .
This means that the client can scroll through the elements found during the recursion, but they do not need to implement their "for each" code as a callback (Java does not have a suitable way to do this) and they can even "suspend" the operation and continue it later , outside the area in which they started it (or leave it anywhere).
This is harder to implement. If the data structure you are viewing is a tree structure with parent pointers in each node, then you do not need any data other than the current node. To go to the next node, find the first child. If there is one, then the next node. Otherwise, try the next brother. If he is not there, get the parent and try to get its next brother, etc., Until you hit zero, in this case there are no more elements.
As a quick and dirty example, here is a treenode-like class that violates all encapsulation rules in order 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 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 describe this for anyone who is familiar with this idea, we want this to be done:
for (final SimpleNode n : new SimpleNodeIterator(root)) System.out.println(n.getIndent() + "- " + n.name);
And get this (I did the above code generated something similar to a hierarchical bullet list in SO):
To do this, we need to map some standard operations to 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 reusable abstract base class that does the rest, now we told him 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); }
(Mildly naughty in that it implements Iterator<E> and Iterable<E> on the same object. It just means that you need to update a new object to repeat a second time, do not try to reuse the same object).
This means that if your hierarchical structure consists of nodes for which you can define these three simple navigation operations, then all you need to do is get your own equivalent to SimpleNodeIterator . This makes it easy to enable this feature for any tree implementation.
If what you are repeating does not have a way to get the parent, you need to save the stack during iteration. Each time you drop to a level, you push the state of the current level onto the stack. When you finish the iteration at the current level, you pop the last state from the stack and continue it. When the stack is empty, everything is ready. This means that you have an intermediate storage, but its maximum size is proportional to the depth of the recursion, not the number of elements, so assuming the data is roughly balanced, it should be much more economical than copying all the elements to the list before you will return.