#1
  1. No Profile Picture
    looking for beautiful code..
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2009
    Posts
    114
    Rep Power
    62

    Talking 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:

    Code:
    // Function to recursively check every item of a nested/tree list
    // Parameters:
    // current_node - reference to the current tree node
    // generation - reference to "level" or "depth" of the recursion 
    // into the loop
    
    function traverse (current_node, generation) {
       // Do any processing/handling of the current node
       ...
    
       // If children exist, loop through them
       // and execute this same function for each item
       if (current_node.children) {
          foreach (current_node.children as current_child) {
             traverse(current_child, generation + 1);
          }
       }
    }
    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:

    Code:
    traverse (rootNode, 0);
    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.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    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 no longer wish to be associated with this site.
  4. #3
  5. Did you steal it?
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    14,054
    Rep Power
    9398
    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.)
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Originally Posted by requinix
    Some designs are much easier* to handle recursively/can't be done iteratively.
    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 .
    I no longer wish to be associated with this site.
  8. #5
  9. No Profile Picture
    looking for beautiful code..
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2009
    Posts
    114
    Rep Power
    62

    Lightbulb


    (* 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.)
    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.

    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
    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?

    I have often wished for an optimizer that could automagically generate non-recursive code from a recursive source.
    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.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Originally Posted by NXInteractif
    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.
    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.
    I no longer wish to be associated with this site.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2005
    Location
    Bay Area, California
    Posts
    841
    Rep Power
    1682
    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.
    Core design principles when developing software systems.
    See my open-source project as an example of professional code.
    ---
    The opinions expressed do not represent those of my employer.

IMN logo majestic logo threadwatch logo seochat tools logo