Re: Implementing recursion (Was Re: Char node-type)

Subject: Re: Implementing recursion (Was Re: Char node-type)
From: Richard Light <richard@xxxxxxxxxxxxxxxxx>
Date: Fri, 24 Nov 2000 10:35:47 +0000
In message <200011240919.JAA29457@xxxxxxxxxxxxxxxxxxx>, David Carlisle
<davidc@xxxxxxxxx> writes
>> Will it not be simpler just to use SAXON -- it recognises tail
>> recursion and implements it using iteration -- therefore no stack
>> overflow will occur.
>But a good question is the algorithm in question tail recursive?
>If it's doing a binary cut and processing each branch with two recursive
>calls then, it isn't...

The original algorithm was, I think.  Here is the relevant named
template, and the text() template which calls it:

<!--process-string: works its way along the string s one character at a
        checking to see if it is in the list of 'normal' characters and
        it if it is not:
<xsl:template name="process-string">
  <xsl:param name="s" select="."/>
  <xsl:variable name="rest" select="substring($s, 2)"/>
  <xsl:variable name="ch" select="substring($s, 1, 1)"/>
  <xsl:variable name="next-text" select="following-sibling::text()[1]"/>
    <!-- this test doesn't work, at least for the MS XSL processor,
because the
        combining character (always an entity reference) isn't part of
the same
        text() string as the character it modifies: -->
    <xsl:when test="($output-encoding='HTML') and (string-
length($rest)&gt;0) and
                                (contains($ASCII-chars-as-string, $ch))
substring($rest, 1, 1)))">
      <xsl:value-of select="'combining char found'"/>
      <xsl:call-template name="process-combining-char">
        <xsl:with-param name="ch" select="$ch"/>
        <xsl:with-param name="combining-ch" select="substring($rest, 1,
    <!-- this variation deals with the MS problem outlined above:
    <xsl:when test="($output-encoding='HTML') and (string-length($s)=1)
                                (contains($ASCII-chars-as-string, $ch))
                                (string-length($next-text)&gt;0) and
substring($next-text, 1, 1)))">
      <xsl:call-template name="process-combining-char">
        <xsl:with-param name="ch" select="$ch"/>
        <xsl:with-param name="combining-ch" select="substring($next-
text, 1, 1)"/>
    <xsl:when test="contains($normal-chars, $ch)"><xsl:value-of
      <xsl:call-template name="process-char">
        <xsl:with-param name="ch" select="$ch"/>
  <xsl:if test="string-length($rest) &gt; 0">
    <xsl:call-template name="process-string">
     <xsl:with-param name="s" select="$rest"/>

<xsl:template match="text()">
 <xsl:call-template name="process-string"/>


Richard Light
SGML/XML and Museum Information Consultancy

 XSL-List info and archive:

Current Thread