RE: [xsl] Recursive Template ??

["Michael Kay" <mike@xxxxxxxxxxxx>]

> > Does it incur a heavy performance penalty ???
> 
> Compared to what?
> 
> For some problems it may be very difficult (if at all possible) to
> have a non-recursive solution.
> 
> Also, often the non-recursive solution (if such exists) is much more
> complex than the recursive one, more difficult to maintain and its
> correctness more difficult to prove.

Very often it's also true that the non-recursive solution is less scalable
than the recursive solution. For example the simple XPath expression to find
the smallest value in a sequence of siblings:

item[not(../item/@value < @value)]

is quite likely to have quadratic performance (if you increase the number of
items by a factor of ten, the cost increases by a factor of 100).

The XSLT solution that relies on sorting the items and taking the first one
in sorted order is likely to have (n log n) performance, which is better.
But a recursive solution is very likely to show only a linear increase,
which is best of all. This means that although it may be slower for small
numbers of items (this depends on how efficient the processor is at doing
function calls or template calls) it will eventually win as the number of
items grows.

On the other hand, if the recursive solution is not carefully written and
carefully optimized, then it may run out of memory when the number of items
becomes too large.

Michael Kay
http://www.saxonica.com/