[xsl] Re: Tail recursion (WAS: Grouping problem?)

Subject: [xsl] Re: Tail recursion (WAS: Grouping problem?)
From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx>
Date: Wed, 23 Apr 2003 23:34:43 +0200
"Conal Tuohy" <conalt@xxxxxxxxxxxxxxx> wrote in message
> 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():


or at a generic sort:


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?


Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list

Current Thread