Is it possible to implement a recursive Algorithm with an Iterator?

Question

I have given a tree like this:

http://www.seqan.de/dddoc/html/streePreorder.png http://www.seqan.de/dddoc/html/streePreorder.png

i can acces each node with the next operator.

// postorder dfs
Iterator< Index<String<char> >, BottomUp<> >::Type myIterator(myIndex);
for (; !atEnd(myIterator); goNext(myIterator)) 
    // do something with myIterator

but i want to use a recursive algorithm on the tree.
Is there a way i can make the recursive algorithm (exlude the biggest subtree on each node) iterative ?
or how i can acces the elements non-recursively ?

Edit: The Actual problem :
I have given a recursive algorithm , that works on trees. (recursive)
I also use a library where i only can acces the Items with an iterator ( non standard , iterative)

recursive <-> iterative.
How can i solve this ?

Answer 1

If your iterator only supports forward (and possibly backward) traversal, but not following links on the tree or fast random access, you will have a very hard time adapting a tree algorithm to it. However, in the end any answer will depend on the interface presented by your custom iterators, which you have not provided.

For example, consider the easy algorithm of tree search. If the only operation given by your iterator is "start from the first element and move on one-by-one", you obviously cannot implement tree search efficiently. Nor can you implement binary search. So you must provide a list of exactly what operations are supported, and (critically) the complexity bounds for each.

Answer 2

You can convert that recursive function to an iterative function with the help of a stack.

//breadth first traversal pseudo-code
push root to a stack
while( stack isn't empty )
    pop element off stack
    push children
    perform action on current node

depending on how you want to traverse the nodes the implementation will be different. All recursive functions can be transformed to iterative ones. A general usage on how requires information on the specific problem. Using stacks/queues and transforming into a for loop are common methods that should solve most situations.

You should also look into tail recursion and how to identify them, as these problems nicely translates into a for loop, many compilers even do this for you.

Some, more mathematically oriented recursive calls can be solved by recurrence relations. The likelihood that you come across these which haven't been solved yet is unlikely, but it might interest you.

//edit, performance? Really depends on your implementation and the size of the tree. If there is a lot of depth in your recursive call, then you will get a stack overflow, while an iterative version will perform fine. I would get a better grasp on recursion (how memory is used), and you should be able to decide which is better for your situation. Here is an example of this type of analysis with the fibonacci numbers.

Answer 3

Any recursive function can alternatively be implemented with stacks. If this is the question you are asking.

Here is an article by Phil Haack on the subject.

Performance gains one way or the other are speculative, the compiler does things with our code behind the scenes that can't always predict. Implement both and get some real numbers. If they are similar use the one that you find more readable.

Answer 4

Even with recursive iteration, you end up with a node-per-node visit.

What you need to know is: how can my iterator be told to go depth-first, and then: how will I be notified that one level has started/ended (i.e. the start/end of a recursion step).

That knowledge can be mapped onto the recursive algorithm.