Re: Tail recursion (WAS: Grouping problem?)

"Conal Tuohy" <conalt@xxxxxxxxxxxxxxx> wrote in message
news:001001c3096e$c36f2700$d9784fcb@xxxxxxxxxxxxxxxxxxxx
> 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