My XSLT Toolbox – Recursive XSLT templates

Recursion is one of the core concepts in programming. It’s valuable not only as a technique for writing programs, but as a general concept for solving problems. XSLT provides many useful elements such as for-each (and apply-templates), but occasionally you will run into a problem which must be solved with recursion. Let’s take a look at a real-world (no Fibonacci!!) example, where we have to operate on a simple string of numbers separated by commas. We’ll take a step-by-step approach to writing a recursive template.

Let’s say we have the following source document, short and sweet. We want to take each number, and wrap it with an element.

<?xml version="1.0" encoding="UTF-8"?>
<comma>1,2,3,4,5,6,7,88,99,100</comma>

The easy way to do this is to use the EXSLT str:tokenize function, which takes a string and some delimiters and splits the string based on those delimiters. All we do is add the xmlns:str and extension-element-prefixes attributes to our xsl:stylesheet declaration, and then call the str:tokenize function.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
version="1.0" xmlns:str="http://exslt.org/strings" 
extension-element-prefixes="str">
 
    <xsl:template match="/>
        <xsl:for-each select="str:tokenize( comma, ',')">
            <xsl:copy-of select="."/>
        </xsl:for-each>
    </xsl:template>
 
</xsl:stylesheet>

The result is, (new-lines added for readability):

<?xml version="1.0"?>
<token>1</token>
<token>2</token>
<token>3</token>
<token>4</token>
<token>5</token>
<token>6</token>
<token>7</token>
<token>88</token>
<token>99</token>
<token>100</token>

Excellent. But let’s say that we don’t have access to the EXSLT functions, and we have to write a template to perform the same thing.

So now we think up a recursive algorithm. Let’s look at a simplified list with three numbers, such as “1,2,3”. First, we print the “1”, the value before the first comma, and then we discard the first comma. At that point, our list will be “2,3” and we repeat, printing the new first value, and discarding the new first comma. Finally, the list becomes only “3”. There is no comma, so we simply print out the rest of the list, “3”. So we will be recursing over the string printing the first number, and then popping off the first number and first comma. This technique will work with a three number list, or a million-number list (though your processor will probably run out of memory before that).

XPath’s “substring-before”, “substring-after”, and “contains” functions are all of the tools that we’ll need to implement our algorithm. “substring-before” lets us obtain the number before the first comma. “substring-after” lets us discard the first number and first comma, and “contains” allows us figure out the last, comma-less case.

Our function starts in the same manner as all recursive functions, dealing with the last case, and then all of the cases before it. The last case will be the comma-less case from our algorithm. So here’s our template skeleton.