Today's programming world is one dominated by imperative programming languages. All of the most popular languages -- Java technology, C (and its various flavors), Visual Basic, and others -- at a high conceptual level, work in basically the same way: You set some variables, call functions or operations that change those variables, and return the result. It is a powerful approach to programming, but it is certainly not the only one.

Another breed of programming languages, while less familiar, are at least equally as powerful as their procedural counterparts. These languages are termed functional or declarative languages. Programs written in these languages may only declare variables once and can never change the value stored by a variable once it's declared. XSL as a programming language is both declarative and functional. This means that developers accustomed to writing in Java code or C and learning XSL often find themselves in foreign territory when using XSL's more advanced features.

Due to the growing importance to both application and Web developers of XML and the related XSL technology, the effective use of XSL transformations cannot be ignored. Thus, it is increasingly important to learn how to program in the declarative fashion. This means becoming intimately familiar with recursion, both its basic usage and the methods for using it effectively and efficiently for the problems at hand.

Introducing recursion by example

Through the use of recursive functions, declarative languages are able to provide the same functionality as their imperative counterparts. This is not to say that imperative languages cannot make use of recursion. Most can. The difference is that declarative languages use recursion as their primary means of operation, whereas it is more often simply a feature in imperative languages.

Consider a function that computes the factorial of some positive integer. As a brief review, the factorial of a number is the number multiplied by all of the counting numbers beneath it. Thus 4 factorial (or 4!) is 4 * 3 * 2 * 1 = 24. Listing 1 shows one way to write this function in Java code:

public int factorial(int number) {
    if (number <= 1) return 1;
    int result = 1;
    for (int i=1; i <= number; i++) {
        result *= i;
    }
    return result;
}

While this is perfectly reasonable code, it does make use of the fact that you can reassign the values of variables in a Java program. Without this luxury, you could still solve the problem by modifying the function as in Listing 2:

public int factorial(int number) {
    if (number <= 1) return 1;
    return number * factorial(number-1);
}

The result of calling either of the two implementations of the factorial method is the same. The call to factorial() within the body of the method indicates that the second implementation is done using recursion. This technique can be visualized like a staircase. The program walks down multiple calls to itself, storing state information for each call until it hits a termination condition. Once it reaches the end, it then walks back up the various states of the calls it has already made, combining the information it stored on the way down to get the final result. The factorial example is shown in Figure 1:

In general, the recipe for creating a recursive function contains three ingredients: the termination condition, the operation code, and the recursive call to itself. For the factorial function, I solved the factorial of n by recursively solving the factorial of n-1, n-2, n-3, and so forth until the function comes to the termination condition of the series, the value 1.

Now, if at this point the concept of recursion still seems a bit confusing, you might want to take a break from this article and either follow some of the links on recursion in Resources or try writing a few functions on your own (for instance, write a function to compute the nth number in the Fibonacci sequence).

Back to top

Common uses of recursion in XSL

Two common scenarios for using recursion in XSL are:

• When you have a set of repeating values in the source XML and you want the transformation result to reflect something about all of those values. For example, if you have a catalog of items in XML and want to present those items along with the price for all of the items, you would have to find that total price using a recursive template.
• When the source XML contains a number x in a tag, for example <countTo number="5"/>, and you want to present some information that same x number of times in the transformation output. The factorial problem is a trivial example of this, but I will examine a more complex example a little later.

I will demonstrate the recursive solution written in XSL for both of these common scenarios, but first let's look at the familiar factorial example solved now in XSL (Listing 3):

<xsl:template name="factorial">
  <xsl:param name="number" select="1"/>
  <xsl:choose>
    <xsl:when test="$number <= 1">
      <xsl:value-of select="1"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="recursive_result">
        <xsl:call-template name="factorial">
          <xsl:with-param name="number" select="$number - 1"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:value-of select="$number * $recursive_result"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

This template has all of the same recursive ingredients as the Java method. There is a termination condition check (looking for a value of 1 or less): If the termination condition is not met, the template makes a recursive call to itself (stored in the recursive_result variable). Finally, the multiplication operation is performed on the original value and the recursively obtained value to get a final result. You may also notice that XSL often requires a lot more typing to get the same job done than other languages. This is just a part of the mixed blessing of having a transformation language that conforms to XML.

Recursion Example 1: Summing across multiple elements

Now you can use the same technique from the factorial example in Listing 3 to find the total price of products in an XML catalog. In fact, the solution is the same as that of the factorial problem, except you are going to use addition instead of multiplication and a node-set as the input instead of a number.

Suppose you have a product catalog that looks similar to the XML excerpt in Listing 4 (by the way, you can download the full XML, XSL, and all other code in this article through a link in Resources):

<Products>
  <Product>
    <Name>Gadget</Name>
    <Price>$10.00</Price>
  </Product>
  <Product>
    <Name>Gizmo</Name>
    <Price>$7.50</Price>
  </Product>
  ...
 </Products>

The goal is to add the first price in the list of products to the sum of all of the other prices until you get to the last price. You can do this with the XSL shown in Listing 5:

<xsl:template name="priceSum">
  <xsl:param name="productList"/>
    <xsl:choose>
      <xsl:when test="$productList">
        <xsl:variable name="recursive_result">
          <xsl:call-template name="priceSum">
            <xsl:with-param name="productList"
              select="$productList[position() > 1]"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:value-of
          select="number(substring-after($productList[1]/Price,'$'))
                  + $recursive_result"/>
      </xsl:when>
      <xsl:otherwise><xsl:value-of select="0"/></xsl:otherwise>
  </xsl:choose>
</xsl:template>

In this solution you are calling the function on successively smaller lists of products, each time adding the first item in the list to the recursive call on the rest of the list. Once the list is empty, the termination condition is reached and you add zero to the result, which leaves the sum unchanged. This technique of working on node lists of smaller and smaller size can be useful in many settings.

Recursion Example 2: Iterating on a number

A second problem that is frequently faced by XSL programmers results when a number is provided in some context in the source XML and the programmer needs to perform a task that number of times. For example, the XML may include information about a grid with a certain number of columns and rows, and the transformation needs to provide a visual layout of the grid in HTML or some other format.

A solution that's commonly used by developers unfamiliar with recursive techniques is to write a program that parses the XML and augments it with elements for each row and column. Once this is done, a simple <xsl:for-each> element can solve the problem without having to use templates or recursion. While this technique will produce the desired output, it has one major drawback: The method effectively doubles the workload of producing the final transformation result. This drawback is particularly noticeable in a client-server model where the server sends the XML and XSL to a client to perform the transformation. In such an instance, all of the efficiencies normally realized by the server are lost in the process of augmenting the XML.

A better solution is to use recursive templates to do the work completely within the transformation. Consider the production of a multiplication table from an XML element into HTML. The input would contain the following line:

<MultiplicationTable Rows="6" Columns="6"/>

The goal is to transform this into HTML that produces a table similar to:

This example is somewhat more intricate than the first two examples. In this case you are not just returning a functional result representing the solution to a problem, but you will output HTML as you step through the recursive process. Also, you need to combine two recursive templates together -- one for the rows and one for the columns.

You can find the entire solution in the mult_table.xsl file that is in the code download included with this article (see Resources). Listing 6 is an excerpt from that file:

<xsl:template name="drawRow">
  <xsl:param name="currentRow"/>
  <xsl:param name="totalRows"/>
  <xsl:param name="totalCols"/>
  <xsl:if test="$currentRow <= $totalRows">
    <tr>
      <xsl:call-template name="drawCell">
        <xsl:with-param name="currentRow" select="$currentRow"/>
        <xsl:with-param name="currentCol" select="0"/>
        <xsl:with-param name="totalCols" select="$totalCols"/>
      </xsl:call-template>
    </tr>
    <xsl:call-template name="drawRow">
      <xsl:with-param name="currentRow" select="$currentRow  + 1"/>
      <xsl:with-param name="totalRows" select="$totalRows"/>
      <xsl:with-param name="totalCols" select="$totalCols"/>
    </xsl:call-template>
  </xsl:if>
</xsl:template>

<xsl:template name="drawCell">
  <xsl:param name="currentRow"/>
  <xsl:param name="currentCol"/>
  <xsl:param name="totalCols"/>
  <xsl:if test="$currentCol <= $totalCols">
    <xsl:variable name="bgColor">...</xsl:variable>
    <xsl:variable name="value">...</xsl:variable>
    <td bgcolor="{$bgColor}" align="center" valign="top">
      <xsl:value-of select="$value"/>
    </td>
    <xsl:call-template name="drawCell">
      <xsl:with-param name="currentRow" select="$currentRow"/>
      <xsl:with-param name="currentCol" select="$currentCol + 1"/>
      <xsl:with-param name="totalCols" select="$totalCols"/>
    </xsl:call-template>
  </xsl:if>
</xsl:template>

In this case I use two separate recursive templates. The first recursively draws the rows of the table one at a time until hitting the termination condition. This template uses the second recursive template to draw the cells for each column in the row one at a time. This general technique is useful for most multi-dimensional data processing.

Back to top

Optimizing recursion patterns in XSL

Unfortunately, the use of recursion in many XSL engines has one major drawback when working with large datasets. It is all too easy to get a Stack Overflow or Out of Memory exception with recursive functions that reach a depth on the order of 10,000. If you are trying to sum prices on a catalog with more than 10,000 items, you may run into trouble.

Fortunately, there are ways to optimize recursive functions to reduce or even eliminate the depth of recursion incurred in a given template. The remainder of this article introduces four methods to optimize how you write your recursive solutions in XSL.

Recursion Optimization 1: Divide and Conquer

Recall the first example in which you tried to find a total price by summing the prices for several items in an XML catalog. The original approach was to add the first item to the sum of all of the rest of the items in the catalog and do so recursively until you had gotten through the entire list. Using this approach, the depth of the recursion is equal to the number of items in the list. Now the goal is to change the technique so you get the same result without going so deep in recursion levels.

A different approach to this problem would be to divide the list into multiple smaller parts and do so recursively until you had divided each part down into a single product. The simplest way to envision this would be by dividing in half the list of products passed in to each recursive call, and then making separate recursive calls on the two resulting lists. This would allow all of the work to complete on one half of the list before any work could be done on the other half. The processing behavior would then be more tree-like than the linear (staircase-like) approach in the previous solution. Figure 2 illustrates this recursion tree.

Using the Divide and Conquer approach, you experience no savings in terms of the number of addition operations that have to be performed. The savings come because the addition operations do not wait until after all of the numbers have been queued onto the recursion stack to perform the operation. The XSL code in Listing 7 demonstrates this point:

<xsl:template name="priceSumDivideAndConquer">
  <xsl:param name="productList"/>
    <xsl:choose>
      <xsl:when test="count($productList) = 1">
        <xsl:value-of
          select="number(substring-after($productList[1]/Price,'$'))"/>
      </xsl:when>
      <xsl:when test="$productList">
        <xsl:variable name="halfIndex"
          select="floor(count($productList) div 2)"/>
        <xsl:variable name="recursive_result1">
          <xsl:call-template name="priceSumDivideAndConquer">
            <xsl:with-param name="productList"
              select="$productList[position() <= $halfIndex]"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:variable name="recursive_result2">
          <xsl:call-template name="priceSumDivideAndConquer">
            <xsl:with-param name="productList"
              select="$productList[position() > $halfIndex]"/>
          </xsl:call-template>
        </xsl:variable>
      <xsl:value-of select="$recursive_result1 + $recursive_result2"/>
    </xsl:when>
    <xsl:otherwise><xsl:value-of select="0"/></xsl:otherwise>
  </xsl:choose>
</xsl:template>

The addition operations take place each time a halved list reaches length one (this being the termination condition) and occur before any processing happens on the second half of the list. Through this technique, the recursion depth never exceeds the log₂ of the number of items in the list, which of course increases exponentially the possible number of product prices to count.

Recursion Optimization 2: Segmentation

Despite the incredible savings in recursion depth provided by the Divide and Conquer approach to recursion, it does have its drawbacks. For lists whose length is not an exact power of 2, the method introduces unnecessary overhead at the tails of the recursion tree.

An alternate approach that still reduces the recursion depth works by iterating across segments of nodes of a predefined length rather than dividing the nodes in half each time. This approach builds on the basic recursion technique, but introduces into it an extra template that acts as a segmentation manager.

The role of the segmentation manager is to break the large problem down into smaller problems that can be handled without concern for running out of memory. The manager keeps track of the results of these smaller tasks, and once they are all completed performs the necessary operation on those results.

You can see an example of the Segmentation technique in the template in Listing 8, which takes a node list as well as a segmentation length, and uses the original price-totaling template to do the work on the smaller segments:

<xsl:template name="priceSumSegmented">
  <xsl:param name="productList"/>
  <xsl:param name="segmentLength" select="5"/>
  <xsl:choose>
    <xsl:when test="count($productList) > 0">
      <xsl:variable name="recursive_result1">
        <xsl:call-template name="priceSum">
          <xsl:with-param name="productList"
            select="$productList[position() <= $segmentLength]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:variable name="recursive_result2">
        <xsl:call-template name="priceSumSegmented">
          <xsl:with-param name="productList"
            select="$productList[position() > $segmentLength]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:value-of select="$recursive_result1 + $recursive_result2"/>
    </xsl:when>
    <xsl:otherwise><xsl:value-of select="0"/></xsl:otherwise>
  </xsl:choose>	
</xsl:template>

Using a Segmentation approach rather than Divide and Conquer reduces overhead in most cases, but does not offer nearly the savings in recursion depth. Which technique is more appropriate for a given problem varies considerably depending on the problem faced. Which one should you use? The answer, as you will see in the next optimization, is both.

Recursion Optimization 3: Combining Divide and Conquer with Segmentation

You can combine the techniques of Divide and Conquer and Segmentation to:

• Maximize the savings in reduction of recursion depth (including the processing overhead associated with each addition level of recursion used)
• Avoid creating overhead at the leaf level of the recursion tree

In this approach, a threshold level is passed to the recursive template along with the node list (or other data to be worked on. Here, the Divide and Conquer method is modified to act as the segmentation manager. If the size of the list passed in is greater than the threshold level, the list is split in half and the template is recursively called on both halves. Otherwise, you use the basic recursion template to compute the result, just as in Segmentation.

Listing 9 demonstrates this technique in the following XSL template:

<xsl:template name="priceSumCombination">
  <xsl:param name="productList"/>
  <xsl:param name="threshold" select="5"/>
  <xsl:choose>
    <xsl:when test="count($productList) > $threshold">
      <xsl:variable name="halfIndex"
        select="floor(count($productList) div 2)"/>
      <xsl:variable name="recursive_result1">
        <xsl:call-template name="priceSumCombination">
          <xsl:with-param name="productList"
            select="$productList[position() <= $halfIndex]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:variable name="recursive_result2">
        <xsl:call-template name="priceSumCombination">
          <xsl:with-param name="productList"
            select="$productList[position() > $halfIndex]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:value-of select="$recursive_result1 + $recursive_result2"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="priceSum">
        <xsl:with-param name="productList" select="$productList"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

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 XSL 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 XSL 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 XSL engine to treat the recursive function as though it were an iterative loop in a procedural language.

Take a look at Listing 10 for the price sum example in Tail Recursive form:

<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 XSL 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.

Back to top

Conclusion

Once you've gained an understanding of the use of recursion, the declarative style of programming in XSL should no longer be an obstacle, but an efficient way of expanding the abilities of XML transformation. The only question remaining is which type of recursion is best for any individual situation.

In general, problems working on small data sets do not call for any of these optimization techniques. However, if a small data set is not guaranteed, the choice is limited by the technology being used in the transformation. If your XSL engine recognizes tail recursion, then that is the best technique to use. If you cannot be assured that the transformation technology will recognize tail recursion, then the combination technique is generally preferred; the threshold value usually ranges in the area of 5 to 30, depending on the problem.

Recursion can be a difficult concept to understand at first, but its usefulness and elegance becomes clearer with use.

Back to top

Bonus Section: Tower of Hanoi

There is a game, familiar to most with a computer science background, called the Tower of Hanoi. The object of the game is to transfer a set of rings from one of three towers to another moving only one ring at a time. The rings have decreasing size and no ring can be set upon a smaller ring on any move. The game has a straightforward solution using a recursive strategy.

To give one last example of recursion in XSL, I have written a solution to the Tower of Hanoi that creates an XML file representing the moves needed to complete the game given the number of rings at the start. A second XSL file converts this solution to a graphical representation in SVG, which you can view in a Web browser with the appropriate plug-in. These two XSL files provide examples of both of the two common uses of recursion in XSL mentioned earlier in the article. You can find both files in the code for this article (see Resources). I have converted the output for a run with three starting rings to GIF format which is shown in Figure 3. Have fun.

Back to top

Download

Information about download methods

Resources

• Participate in the discussion forum.
  
  
• Download the zip file containing all of the code related to this article (see the README file for usage notes).
  
  
• Download Xerces (XML parser and DOM implementation) and Xalan (XSL transformer) from the Apache XML Project if you need a good XML or XSL implementation.
  
  
• Read articles and explore tutorials on XML/XSL:
  • Mark Colan's article on XSL: "Putting XSL transformations to work" (developerWorks, October 2001)
  • Dan Day's article on XSL: "Hands-on XSL" (developerWorks, March 2000)
  
  
  
• XSLT as a Functional Language:
  • Michael Kay's article on XSL: "What Kind of Language is XSLT?" (developerWorks, February, 2001)
  • Dimitre Novatchev's articles on XSL as a functional language: "The Functional Programming Language XSLT - A proof through examples" and "Dynamic Functions using FXSL: Composition, Partial Applications and Lambda Expressions".
  • Find more XML resources on the developerWorks XML zone.
  • Check out Rational Application Developer for WebSphere Software, an easy-to-use, integrated development environment for building, testing, and deploying J2EE applications, including generating XML documents from DTDs and schemas.
  • Find out how you can become an IBM Certified Developer in XML and related technologies.
  
  
  

About the author

Jared Jackson is a Researcher at IBM's Almaden Research Center. He works in the area of Web-based technologies.

Comments (Undergoing maintenance)

Back to top

Trademarks  |  My developerWorks terms and conditions

Table of contents

• Recursion by example
• XSL recursion uses
• Optimize XSL patterns
• Conclusion
• Bonus: Tower of Hanoi
• Download
• Resources
• About the author
• Comments

Next steps from IBM

With the no-charge DB2 Express-C, pureXML, Zend Core PHP, and Java you can develope advanced Web 2.0 applications quickly that matter.

---

• Try: Download a free trial version of DB2 Express-C, which includes Zend Core PHP and pureXML technology that is ideally suited for managing both XML and relational data.
• Article: See how DB2 pureXML schema capabilities can evolve schemas without making any changes to your applications.
• Tutorial: This tutorial shows you how to use DB2's pureXML to expose the native XML capabilities of DB2.
• Buy: DB2 9 for Linux, UNIX and Windows

My developerWorks community

Dig deeper into XML on developerWorks

Rate a product. Write a review.

Write a review for Rational products today!

Special offers