Generic recursive algorithm for nested/tree lists

Just a quick pseudo-code algorithm for those like me who find the need over and over again for a way to traverse all items of a nested or tree-based list:



The initial use of this function should use the top-most node of the list as the first parameter and the value 0 for the second as follows:



Just wanted to put this out there because time and time again I face this same problem, and every time I forget how to start off.

-j.

It's not a vary useful algorithm is it? I mean, it's recursive. Ok for working out the algorithm, but then you have to convert that to something you can actually use with real data and that usually means you have to convert it to an iterative rather than recursive form.

I quite like the iterative approach. Makes me feel clever.

- Start with a list of items to traverse. At first it only contains the root item
- Start with a counter=0
- Do:
- - Do your work on the counter-th item in the list
- - Add its children to the end of list
- - Increment counter
- Loop until counter has passed the end of the list

Depending on the language it might be easier to do shift/push operations on the list instead of keeping a counter (better on memory usage too).

Mind you, you can't always use this for some "do your work" design. Some designs are much easier* to handle recursively/can't be done iteratively.

(* Blah blah blah, because new programmers are taught the magic of recursion and so they think recursively from an early start without being educated much on why recursion can be bad and when and how they should avoid it.)

Easier perhaps, but never impossible. In fact, it's usually a simple step to convert from recursive to iterative. I often debug in the recursive form first, to avoid having the complications of the iterative over-head, then when the algorithm is properly implemented and test at least to the depth available on the stack, I convert it to the iterative form and run my unit tests against it.

But I am thinking in C/C++, Pascal and Ada where function calls generally use a stack with some size limitations. Some functional languages actually manage to do recursion quite nicely without ever blowing the stack. I have often wished for an optimizer that could automagically generate non-recursive code from a recursive source. Then I would have the best of both worlds .

Um? How exactly do you figure that? In fact, I'd think most new programmers would tend toward an iterative approach first because they only look at a single instance for each method's implementation (a very bad approach to design patterns and internal architecture).

In addition, requinix, your approach processes everything in order going from all top-level elements, then all secondaries, and so on, however, it never once retains the current count on the level/generation of each element. So if someone wanted to use this algorithm to process every element of a tree except for items in the second level/generation, there would be no way for your approach to determine whether or not to process certain elements (unless each element had its own "level" or "generation" property built-in, which isnt very likely to be built-in to most data structures).

In addition, if any sort of fail-safe error handling is introduced to such an algorithm, and assuming an error is present on the 2nd top-level element, using your iterative method will halt all operations at the top level while never traversing the child elements or children of the child elements on the first top-level element.



Do you at all see the use of pseudo-code as a giant clue that maybe this isnt directly focused on one application of such an algorithm? There is no reason why using "real data" would affect this design approach. There is no feasible way to account for all pieces of data when it is either unknown or it ranges in an undefined dimension.
In addition, how could the majority of "real data" (given that it is structured as a tree or nested lists) have to be processed only in an iterative manner?



But yes I would have to agree with you completely that it would be nice for this to be available, but I'd imagine the reason why this hasn't become effectively available is the fact that recursion cannot be predicted given a variable or undefined length of data. Of course, maybe in C# where something like MSIL runtime compiling functionality is present, this may be possible to generate the iterative version of a recursive function based on whatever data has been loaded at runtime, therefore reducing some excess overhead. However, again, this is algorithm here is taking a broader approach to such a design.


In short, recursion, though it may make a mess of stack management, implements a much clearer and more elegant design. So even if you can whip up an iterative version of a recursive function, it is much easier to start off by implementing a recursive function and reducing it as necessary. However, for tree-based lists (which this entire thread has been posted for), it is almost more advantageous to use recursion as a method of increasing modularity in solving complex problems using data that is structured as a tree.
In addition, this whole thread is meant for conceptual analysis rather than saying that "this will not work for me with my application."

-j.

I thought that some functional languages avoid that problem by not using the stack for obviously recursive functions. Was it Haskell? I don't remember where I read that. I suppose any interpreted language could be implemented with or without local variables being pushed on the stack.

Most functional languages use a compiler that support tail recursion, which transforms the recursive expression into an iterative one when possible. That can occur when the recursive call is the last operation of the function, so there is need to maintain the call stack. Most of the time a recursive function can be rewritten into a tail-recursive form, such as by using an accumulator to pass state between invocations. The only problem with tail recursion can be ease of debugging and sometimes a slightly more verbose definition.

Note that this is a compiler optimization and not a language feature. Since recursion isn't favored in Java, the data structures such as TreeMap use iterative forms. Alternative languages like Scala and Clojure favor it, but must try to detect and optimize it in their byte-code generators. This has had limitted success, so support was added to the JVM in JDK7.

You can easily blow away the stack in Haskell, but tail recursion and lazy evaluation can help reduce that from happening.