"Conal Tuohy" <conalt(_at_)paradise(_dot_)net(_dot_)nz> wrote in message
news:001001c3096e$c36f2700$d9784fcb(_at_)insurgentes(_dot_)local(_dot_)(_dot_)(_dot_)
Dimitre wrote:
You can use a DVC (Divide and Conquer) style algorithm here. Split a
node-set into two and recursively solve the problem on them.
<snip/>
The recursion depth of a DVC algorithm is only log2(N).
http://www.topxml.com/code/default.asp?p=3&id=v20020107050418
OK - log(n) is better than (n), but why use a DVC algorithm to minimise
stack-depth if a tail-recursive algorithm would eliminate the procedure
stack altogether?
The reason is simple enough -- why be dependent on unknown and unproven
claims and statements about the tail-recursive optimization capabilities of
version X of XSLT processor Y, why intentionally destroy the portability of
the code and bind it only to a select few XSLT processors?
Saxon is a happy exception of the rule, but even in Saxon some cases of
tail-recursion optimization are implemented (e.g. recursively calling a
named template) while others are not -- see a recent post by Mike Kay
explaining this.
Using a DVC algorithm it is not meaningful at all to worry about the size of
the call stack, therefore not meaningful to try to eliminate it -- the
problem simply doesn't exist in any practical case. For example, a DVC 1
MB-string reversal transformation needs a call stack of only 19 elements.
Another reason to use DVC is that many DVC algorithms look simpler and more
elegant. Look for example at a DVC max():
http://www.topxml.com/code/default.asp?p=3&id=v20030314165921
or at a generic sort:
http://www.biglist.com/lists/xsl-list/archives/200303/msg00007.html
So I'd reverse your question: Why not implement a DVC algorithm, when it's
the only efficiently-working solution in the general case, is much more
portable, reliable and aesthetically appealing?
=====
Cheers,
Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list