[xsl] Recursion Was: Re: 2 Questions: (1) about looping...

Subject: [xsl] Recursion Was: Re: 2 Questions: (1) about looping...
From: Joerg Pietschmann <joerg.pietschmann@xxxxxx>
Date: Tue, 28 Aug 2001 12:22:19 +0200
Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote:
> You can organise a loop in XSLT using either:
> 
>   1. Simple recursion, where a template processes one member of a list and then
> calls itself recursively to process the rest -- see for example:
[snip] 
> From the above three, the first works efficiently only on relatively short lists,
> getting an exponential-time behaviour very soon when the length of the input list
> increases. It also crashes existing XSLT processors (with the exception when
> "tail-recursion" and XSLT processors optimised for tail-recursion are used). The
> maximum call-stack depth is N - 1.
> 
I have to comment on this.
The following code will not crash Saxon even if you start it with i=1000000
and it wont slow down exponentially:
  <xsl:template name="foo">
    <xsl:param name="i"/>
    <xsl:if test="$i &gt; 0">
      <xsl:text>*</xsl:text>
      <xsl:call-template name="foo">
        <xsl:with-param name="i" select="$i - 1"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>
Some not quite representative execution times as measured by saxon -t
(includes some overhead):
      i  time (ms)
     10    161
    100    170
   1000    290
  10000    441
 100000   5358
1000000  54579
As you see it's somewhat superlinear asymptotically but hardly worth
arguing about it.
The following variant does the same but will crash already for i=1000
  <xsl:template name="bar">
    <xsl:param name="i"/>
    <xsl:if test="$i &gt; 0">
      <xsl:variable name="result">
        <xsl:text>*</xsl:text>
        <xsl:call-template name="bar">
          <xsl:with-param name="i" select="$i - 1"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:value-of select="$result"/>
    </xsl:if>
  </xsl:template>
Optimizing tail recursion implies that local variables must not be
held across the recursive invocation. The code above makes it worse
by O(n^2) space allocation (the length of the result variable grows
linearly, because they are all in memory at the same time this adds
up to O(n^2)).
Conclusion: properly implemented text-book recursion works, even on
large input values/long lists, if the processor is good enough.
Divide-and-conquer/binary split techniques may have an adavantage
nevertheless due to limited recursion depth, especially if potentially
large string buffers are involved. However, the larger overhead of
divide-and-conquer techniques is always a disadvantage for small
problem sizes.
D.Knuth discusses this at length in his famous book series "The Art
of Programming", especially in Vol.3 (Sorting and Searching) but
also in the "General" section of Vol.1.
Interesting comments about traps and pitfalls in tail recursion
optimisation can be found in the gcc source code. The Dragon
books discuss this also.

Regards
J.Pietschmann

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


Current Thread