Recursion Optimization 4: Tail Recursion
If you already have some experience with recursion, you are probably wondering why I didn't mention Tail Recursion as the first optimization technique, since this technique can eliminate recursion depth completely without introducing any substantial overhead. Despite the advantages this technique offers, it requires that the XSLT engine doing the transformation recognize the presence of the technique within the XSL code and then change its behavior to accommodate the technique. Unfortunately, most XSLT engines do not yet offer such a feature.
The good news is that the overwhelming acceptance of XSL in the business and academic worlds means that this limitation will not be with us too much longer. It is therefore important for developers to understand how Tail Recursion works, as it may eliminate the memory problems many now face without hindering performance in any substantial way.
The basic idea behind Tail Recursion is to eliminate the storage of any state information across the recursive steps. All information that would ever be needed at any single step is passed as a parameter to the function instead of being stored at some higher level in the recursion stack. This allows the XSLT engine to treat the recursive function as though it were an iterative loop in a procedural language.
<xsl:template name="priceSumTail">
<xsl:param name="productList"/>
<xsl:param name="result" select="0"/>
<xsl:choose>
<xsl:when test="$productList">
<xsl:call-template name="priceSumTail">
<xsl:with-param name="productList"
select="$productList[position() > 1]"/>
<xsl:with-param name="result"
select="$result +
number(substring-after($productList[1]/Price,'$'))"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise><xsl:value-of select="$result"/></xsl:otherwise>
</xsl:choose>
</xsl:template>
The addition of the extra result variable makes all of the difference. Instead of stacking numbers to add at the various recursive steps, the addition is done at each stage and the result passed along as a parameter to the next recursion step. A smart XSLT engine would simply overwrite the memory space holding the result value on each call in the same manner that a variable value is overwritten in Java code or C. This technique allows the language to take advantage of the features of both declarative and imperative language processing without changing the nature of XSLT as a programming language.