Recursion makes my brain hurt

[Andrew McLaren]

I am attemping to parse through an XML document, which in oversimplified form looks kinda like this:

<root>
<folder>
<table>...</table>
<folder>
<table>...
</folder>
</folder>
</root>

Since I could theoretically have any number of nested <folder> elements, I guess the only way I could do this is through recursion, yes? But I am not entirely sure I have a solid grip on how recursion works. If I have something like 5 nested calls to same method, will Java work it's way back up in the correct order, until I reach the top call?

I hope this makes some semblance of sense.

Thanks!

Andrew

[Peter Chase]

Yes, such recursive calls will work fine, and are used by many programs. There is a limit to the depth of call nesting, according to the Java stack size. However, it is a limit that very few real-life programs will reach and not something to worry about as a beginner. It is certainly unlikely that your XML document would be sufficiently nested to cause such problems.

[Ryan McGuire]

Originally posted by Andrew McLaren:

Since I could theoretically have any number of nested <folder> elements, I guess the only way I could do this is through recursion, yes? But I am not entirely sure I have a solid grip on how recursion works. If I have something like 5 nested calls to same method, will Java work it's way back up in the correct order, until I reach the top call?

Yes and yes.

Of course you have to careful with what you do at each level of recursion. If you'd like to take a stab at some code and post it here (using CODE tags, naturally), I'm sure someone would be happy to give you some help with any problems you're having.
[ December 01, 2005: Message edited by: Ryan McGuire ]

[Ernest Friedman-Hill]

Andrew --

Parsing XML is complicated by all sorts of little ugly details, which is why there are a number of standard APIs for XML parsers, and a multitude of available XML parsers that do the whole job for you. For an extremely, extremely simple document, you might be able to justify doing it by hand, but given what you describe, I hope you're instead using an existing parser, and you're simply asking us about recursively examining the parser's output (a DOM tree, for example.)

See here if you're not sure what I'm talking about.

[Andrew McLaren]

Thanks for all the replies. This is a pretty big lead forward for me, so we'll see how it goes.

And yes, I am using dom4j. I couldn't even imagine trying to write my own parser.

Peace

Andrew

[Stan James]

Your recursion will probably look something like:

process( root );
 
void process( Node node )
{
   print the node tag and value <- just for debugging
   get all children of node
   for each child
      if node is "folder"
         process( node ); <- recursion happens
   next
}

Draw out an XML doc with a couple nested folders, follow this through and write down what it would print. I had to do recursion on paper this way many times before it came naturally. It takes a little effort to remember just where to "pop back" when you return from the nested call.
[ December 01, 2005: Message edited by: Stan James ]

[Andrew McLaren]

Originally posted by Stan James:
Your recursion will probably look something like:

process( root );
 
void process( Node node )
{
   print the node tag and value <- just for debugging
   get all children of node
   for each child
      if node is "folder"
         process( node ); <- recursion happens
   next
}

Draw out an XML doc with a couple nested folders, follow this through and write down what it would print. I had to do recursion on paper this way many times before it came naturally. It takes a little effort to remember just where to "pop back" when you return from the nested call.

[ December 01, 2005: Message edited by: Stan James ]

Here's what I came up with (liberally pillaged from the dom4j cookbook):

public class ModelWalker {
    
    public void modelWalk(Document document) {
      System.out.println(document.getRootElement().getName());
      modelWalk( document.getRootElement(),document );
    }
    
    public void modelWalk(Element element, Document document) {
      System.out.println(element.nodeCount());
      for ( int i = 0, size = element.nodeCount(); i < size; i++ ) {
        Node node = element.node(i);
        
        if (node.getName().equals("folder")) {
          Element elem = (Element)node;
          Attribute attrib = elem.attribute("name");
          System.out.println("Folder name:  "  + attrib.getValue());
          modelWalk( (Element) node,document );
        }
...  

It definitely took me a few stabs to get it going, but it looks to be working so far!

[Stan James]

Very cool! Keep it fun!