Walking the DOM (was: XML APIs)

[Tim Bray]

At 12:50 PM 11/3/98 -0500, John Cowan wrote:
>Stephen R. Savitzky wrote:
>
>> [T]he classic algorithm for traversing a tree is:
>> traverse(node) {
...
>> }
>
>The trouble with that algorithm is that it is recursive.  It will
>blow up if the tree is sufficiently deep.  Indeed, in
>languages that cannot be relied on to do tail recursion, like
>Java, it will blow up if the tree is merely sufficiently wide.

Wouldn't the effects of recursion will be lost in the static,
compared to the effects of loading the doc into memory to facilitate
tree processing?  Even if you are doing some persistent-ancillary-
info trick to do a virtual tree, in my experience for very large
docs you really have to wrangle memory carefully.  It seems
really counter-intuitive that the stack & local variables overhead
caused by recursion is going to get you before one of these
other things.   Unless of course you recurse in some huge
sloppy badly-written routine with lots of local junk.

BTW, what languages can be relied on to do tail recursion?

Also, shorter algorithms are better. -Tim


xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo at ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)