Day 17
Using Recursion

In yesterday’s lesson, you learned some additional techniques for selecting and matching data in an XML source. You learned that keys and ID type values defined in a Document Type Definition (DTD) can speed up data retrieval, or at the very least make it easier to select certain data.

NEW TERM

Today’s lesson is again about operating on data and will cover only one important topic: recursion. Recursion is a technique rather than an element or a function, and it is mostly used in situations in which iteration isn’t sufficiently powerful enough.

In today’s lesson, you will learn the following:

• What recursion is

• How to use recursion

• How recursion can help you get around some of XSLT’s limitations

• What the drawbacks of recursion are

Understanding Recursion

Recursion is a powerful, useful, but sometimes tricky technique that can be used in place of iteration, which you’re already familiar with. Recursion and iteration are similar, but with recursion you can perform tasks that are not possible with simple iteration.

What Is Recursion?

Recursion is a common construct in programming. It occurs when a function or a template calls itself. A function calling itself sounds a little odd because a function is called to perform a certain task. Why call it again to perform that task? The idea is that the task the function needs to perform can be broken into smaller tasks. These tasks are the same as the original task, but smaller. To solve that task, you can call the same function, which will, in turn, break the task into smaller pieces and call itself again. This process goes on until the task is so simple that it can be performed without calling the function again. The last time the function is called, it returns a result. The function that called the last function performs its small part of the work and tags on the result from the function it called. It then returns the result so that the function that called it can do the same. This process goes on until the first function that was called does its part and tags on the result from the function it called. It then returns the final result to its caller.

Your head is probably spinning by now, so let’s look at a common example of recursion in mathematics. The factorial of 5, written as 5!, is a great example of recursion. 5! is equal to 5*4*3*2*1. The result can be calculated by breaking the calculation into several smaller pieces—for instance, (5*4)* (3*2)*1, which is equal to 20*6*1. If you calculate the result of 5! using recursions, it looks like the representation shown in Figure 17.1.

FIGURE 17.1 Visual representation of recursive function calculating 5!.

The boxes in Figure 17.1 represent the function that is called to perform the calculation. The arrows on the left show the call with the value given to calculate. In the boxes, you can see how the function breaks down the calculation. Each time, the function takes off one multiplication and then calls itself to calculate the remainder, which is shown between the parentheses. The arrows on the right show the result of each step in the calculation. You can check that the result of 5! is indeed 120 by substituting the factorial in the box with the result calculated up until then. The smallest box no longer has to break down the calculation because only two numbers are left to multiply. The result of that multiplication is multiplied by the number that was taken off by the function above it. This process continues until the top function returns the final result. You can see that for each calculation the same algorithm is reused to create the desired result.

Why and When Should You Use Recursion?

Using recursion is an elegant way to solve problems. If you can define a problem in its smallest form and create a function or template to solve that problem, that problem can be solved no matter how big it is. The only limit is the one imposed by the computer and/or the processor. Because of the way a recursive function solves a problem, it is often quite small—smaller than any code that solves the same problem without recursion. In XSLT, several tasks are impossible to perform without recursion; the calculation shown in Figure 17.1 is one of them.

So, why can’t you solve such problems without recursion? The answer is quite simple: The value of a variable is unchangeable as long as it is in context. Therefore, you can’t use a simple calculation line such as myvar = myvar + 1. If that weren’t the case, you could have used iteration instead of recursion to solve the factorial example. For instance, in Visual Basic, you would make the same calculation as follows:

Result = 1
For i = 1 To Factorial
  Result = Result * i
Next

This code is much simpler because, with each iteration, the value of i is increased by 1, and the result is created from what you already had. When you use recursion, this use of a variable is actually simulated each time you pass the parameter’s new value to the next template call.

A textbook example of a problem that can be solved well with recursion involves a traveling salesman. In this problem, the salesman has to visit a number of cities. You have to find the quickest way for the salesman to visit all of them. The way to solve this problem is to break the tasks into smaller pieces again. Say the salesman has to visit five cities. In that case, you start with a city and then calculate the quickest way to visit the other four cities. You do so by calculating the quickest way to visit the remaining three, plus the time for the fourth city. Just as with the factorial problem, you end up with just the time required to go from one city to another, which is easy to calculate.

Such problems occur most of the time in XSLT when there is no way to iterate using templates or xsl:for-each. This situation happens most often when you have to operate on the value of an attribute or element with no child elements or anything. In that case, you have just the raw data. Consider the following example:

<name=Tuco Benedito Pacifico Juan Maria Ramirez</name>

You’re probably thinking that it would be better to store this name as follows (and you would be right):

<name>
  <firstname>Tuco</firstname>
  <firstname>Benedito</firstname>
  <firstname>Pacifico</firstname>
  <firstname>Juan</firstname>
  <firstname>Maria</firstname>
  <lastname>Ramirez</lastname>
</name>

The second format is much better because you can work with the first names separately and separate from the last name. If you wanted to output Tuco B. P. J. M. Ramirez, you could easily do so with the second format. You can just use xsl:for-each to iterate through each firstname element and then use the substring () function to get the first letter. With the first format, you can’t do that. You have to keep track of where you are in the string somehow. The only solution here is to use recursion. This approach would, of course, also enable you to reformat the first format into the second. If you designed the original document, you probably would go for the second format, but you will find that when you start working with XML documents created by others, data such as that used in the first format is not uncommon. The only thing to do is to deal with it. Recursion gives you the opportunity to do so.

The Drawbacks of Recursion

The fact that recursion is elegant and can solve problems that are otherwise unsolvable doesn’t mean you should always use it. When you can solve the same problem by using template matching or xsl:for-each, go for it. In most cases, such a solution will perform better. Depending on how smart the processor is (or actually the compiler that’s part of the processor), recursion can cost a lot of memory and performance. When you use recursion, the processor has to keep track of how many times a template has been called and what the state of each template is. Doing so costs memory, and this memory usage can increase rapidly. When the processor runs out of memory, it will fail, and fail badly. The likelihood that this failure will happen with matching or iteration is much smaller because the memory usage of these mechanisms is much lower.

NEW TERM

Whether recursion performs poorly also depends on the compiler. If the compiler can detect that a function is recursive, it can cut down on both memory usage and execution time because it can treat the recursive code almost as if it is iterative code. Detecting whether code is recursive, however, is by no means easy. A variant of recursion that is relatively easy to track down is called tail recursion, which is the case when a template calls itself on the last line of the template (or at least if there are only closing tags after it).

A major problem of recursion is that it needs to end somewhere; otherwise, the template would just keep calling itself until the program fails. So, you need to make sure that the template checks when it has to return to its caller without calling itself again. With a simple template, this check is easy, and either you return immediately, or you call the same template again. When this check becomes complex, the likelihood increases that you haven’t covered all the bases, in which case you get a never-ending piece of code—never ending, that is, until the processor fails.

Creating Recursive Templates

In XSLT, you can’t create recursive functions. In fact, you can’t create functions. Period. The only way you can create functions is to extend the processor, which is the topic of Day 20, and cannot be considered as XSLT itself. That said, you can create recursive templates.

Recursive templates call themselves using xsl:call-template. Using xsl:apply-templates wouldn’t make sense because then you have no way of knowing for sure that the correct template is processed. Recursion builds on the fact that it processes the correct template because each time the template is called, a smaller version of the original task has to be executed. If you go on to an entirely different template all of a sudden, then that is no longer true. One exception here occurs when you have templates that call each other in a circular fashion; for instance, template A calls template B, which calls template C, which calls template A again. Although, in the strictest sense, this example is not recursion, it is the same thing; the functionality is just broken into several templates instead of everything in one.

The basis of a recursive template looks like this:

<xsl:template name="recursivetemplate">
  <xsl:call-template name="recursivetemplate" />
</xsl:template>

The preceding code is not enough. The template will call itself again and again. There is never a way out, so eventually this code will fail because the processor will run out of memory. To solve this problem, you should create the code so that it at least looks like this:

<xsl:template name="recursivetemplate">
  <xsl:if test="recursionclause">
    <xsl:call-template name="recursivetemplate" />
  </xsl:if>
</xsl:template>

The xsl:if element makes sure that the template calls itself only if recursionclause returns true. This is actually the tricky bit because the result of this clause will not change unless you have some way of changing values. Variables in XSLT, however, cannot change, and even if they could, they go out of scope. The solution is to use parameters, so you can create a template that returns a result based on the parameter. Because the template also has to return values, more changes over the preceding code are required. Listing 17.1 shows a stylesheet with a proper recursive template that actually implements the factorial function discussed in the preceding section.

LISTING 17.1 Stylesheet Implementing the Factorial Function

Note

ANALYSIS

The recursive template in Listing 17.1 starts on line 13. On line 14, a parameter named num is defined with a default value of 1. Whether the template calls itself again is decided with an xsl:choose element. The only xsl:when element is on line 16. It checks whether the value of the num parameter is 1. If it is, the last value of the factorial multiplication row is reached, and no multiplication is needed. Therefore, only the value of the num parameter has to be returned, which is done on line 17. Any other code is ignored, so the call for which the test expression on line 16 is true is the last template to be called—the escape hatch, as it were.

What happens inside the xsl:otherwise element is actually much more interesting. The template calling the same template again on line 21 sits inside a variable, defined on line 20. So, any values written in the called template will become the value of the variable. That result is the result of the same task performed on a smaller number. This is what the xsl:with-param element on line 22 is for. It calls the same template again, but with the value of the num parameter minus 1. The result of this call is multiplied by the current value of the num parameter. Therefore, the result returned to the caller is the result from the called template multiplied by the value of the num parameter within the current template. This stylesheet doesn’t actually depend on any XML source. Line 9 calls the calculate template with the hard-coded value 6. So, if all is well, the result is always 720. Listing 17.2 is much more intelligent.

LISTING 17.2 Stylesheet Showing Recursive Steps

Note

ANALYSIS

Listing 17.2 depends on a global parameter that can be set from outside the stylesheet. Setting this parameter enables you to run the code for different numbers. In addition, lines 17, 21, and 30 contain an xsl:message element. This element doesn’t create any visible output normally but writes a message to a separate output stream. This output stream is used for reporting, such as reporting errors or timing information. When you run a processor from the command line, this output also appears, but it doesn’t interfere with processing or alter the output from the stylesheet itself. You can see this very well when you tell the processor to send the output to a file. For instance, with Saxon, you can type

saxon -o out.txt 17list02.xsl 17list02.xsl factorial=7

With MSXSL, you can run the stylesheet from the command line as follows:

msxsl -o out.txt 17list02.xsl 17list02.xsl factorial=7

Caution

This command sends the output from the transformation to the file named out.txt. Note that because you don’t need an XML source, you can give any XML source. I just used the stylesheet as XML source as well. The output in the file will just be the result, which is 5040. In the command window, you can see the output from the xsl:message elements. You can use xsl:message during development to keep track of what’s happening, similar to xsl:comment, with the difference that xsl:comment creates output as part of the stylesheet’s result. This means that xsl:comment is not usable in a situation in which a template returns a result that should be processed.

Recursion with Single Values

As I explained in the preceding sections, working with single data values that arguably should have been broken up into elements or attributes can cause trouble. When such a value has a rigid structure, you can get away without using recursion because you know the structure at design time. This means you can break up the value into discrete pieces with functions such as substring (), substring-after (), and substring-before (). Data like that shown in Listing 17.3 is an entirely different matter.

LISTING 17.3 XML

ANALYSIS

The data values in Listing 17.3 are dynamic. By that, I mean that you have no idea at design time how many first names a full name contains. Therefore, you can’t just use substring-after () and substring-before () to get to each of the first names. Well, you can, but not without recursion. Recursion enables you to operate on such data because it enables you to dynamically move through the data. Listing 17.4 shows this use effectively.

LISTING 17.4 Stylesheet Using Recursion to Initial First Names

ANALYSIS

Listing 17.4 initials all the first names of the full names in Listing 17.3. This process is mostly performed by the recursive template on line 18. The value it processes is the fullname parameter defined on line 19. The template assumes that the string value it gets is normalized, so before the template is called for the first time, line 13 normalizes the name value. This means that all names are separated only by spaces and that there is no leading or trailing whitespace. The escape hatch for the recursive template is the situation in which no more spaces exist in the name passed to the template. At that point, only the last name is left. The xsl:otherwise element on line 29 is there to deal with this situation. All that is done in this case is writing the name, which occurs on line 30. The recursive part of the template is handled by the xsl:when element on line 21; this part is processed if spaces still exist in the name—in other words, when first names are still left. Because first names still exist, the first letter of the entire value is the first letter of the first name to be initialed. Line 22 therefore uses the substring () function to write just the first letter of the value. Line 23 follows up with a period and space. Line 24 calls the template again, with line 25 providing the new name to be processed. This name should be the current value minus the first name just handled. Because the names are separated by spaces, you can easily get this value by using the substring-after () function. Applying Listing 17.4 to Listing 17.3 yields the result in Listing 17.5.

OUTPUT

LISTING 17.5 Result from Applying Listing 17.4 to Listing 17.3

Totaling with Recursion

The computational capabilities of XSLT are limited. In fact, they are so limited that for computations that go just a little beyond the basics, you have to be creative. In many cases, you end up with a recursive solution. This section discusses a common scenario for e-commerce sites, where you have an inventory and an order combined with the inventory data to create an invoice, and so on. The example given here is based on the familiar menu document shown in Listing 17.6.

LISTING 17.6 XML Source Representing an “Inventory”

ANALYSIS

In the menu data in Listing 17.6, each dish element has an id attribute. In the preceding chapters, you didn’t use this attribute. Now, however, these values are needed to uniquely identify each element because the order information in Listing 17.7 refers to these id attributes to define the order.

LISTING 17.7 XML Source with Order Data Related to Listing 17.6

ANALYSIS

Listing 17.7 shows an order from a party of five taken by the waiter (probably after he punched it into the computer). Each dish ordered is identified by the id attribute; how many times that dish is ordered is given by the quantity attribute. When the dinner party asks for the check, Listing 17.8 springs into action and creates a nice-looking list of dishes ordered and the total.

LISTING 17.8 Stylesheet That Creates a Check Based on Listings 17.6 and 17.7

ANALYSIS

Listing 17.8 is used to process Listing 17.7. The data about the dishes in Listing 17.6 is loaded into a variable named dishes on line 7. Before going recursive, the stylesheet uses matching on line 10 to display each dish ordered with its price, quantity, and the price multiplied by the quantity. For each order element, this is done with the template on line 17. Apart from the template getting the data from each ordered item from the dishes variable, not much is going on there. The interesting part of this template is, of course, calculating the total, which is done with the template on line 28. It is called from line 12, with line 13 passing the entire node-set with order elements to the order parameter. Each time the template calls itself, it takes off one element. This element is added to the total in the same call of the template. The template returns without calling itself again if the node-set is empty. Line 43 makes sure that the value returned in that case is 0. Line 31 checks whether the node-set is empty, and if it’s not, line 32 creates a variable named subtotal. This variable gets its value from calling the template again. Line 34 passes the parameter, with the selection on line 35 selecting all nodes currently in the node-set, except the node in the first position. It is the node that this template does the calculation for. The subtotal to be returned is created from the subtotal returned from the template call, plus the price of the dish being handled by this template multiplied by the quantity. All these calculations are performed on lines 40 and 41, with the lines before that getting the price from the dishes variable. The result is shown in Listing 17.9.

OUTPUT

LISTING 17.9 Result from Applying Listing 17.8 to Listing 17.7

ANALYSIS

Listing 17.9 shows a nice little check, indicating the number of times each dish was ordered, the price of the dish between parentheses, and the subtotal for that dish behind it. Finally, the last line shows the result from totaling with the recursive function.

Summary

In today’s lesson, you learned that recursion is a technique to be used when all else fails. This situation usually happens when values have a dynamic feature that can’t be dealt with by simple matching and iteration. Using recursion is also a common solution to the drawback that variables can’t change while they are in scope.

You also learned that although recursion is elegant, using it everywhere is not a good idea. If you can use matching and iteration, doing so is likely to be much better for performance. This fact is not surprising because this is what XSLT is good at. Recursion can be inefficient because it is implemented using a template that calls itself. Each call costs memory and, unless the compiler is smart, processing cycles as well.

Tomorrow’s lesson will pick up where this lesson ends: the computational power (or lack thereof) of XSLT.

Q&A

Q Is there a limit to the number of times a template can call itself?

A Theoretically, no. There is, however, a limit to the memory a processor has available. Because each call costs memory, memory will eventually run out, and the processor will terminate.

Q Can I use all the elements in a recursive template that I can in any other template, matched or called?

A Yes. A recursive template is not different from any other. The only difference is that it calls itself again instead of invoking other templates through matching or calling.

Q Where do I start when I need to make a recursive template?

A Take the problem you have in its smallest form. This is typically just one operation. It should at least be an operation that can be solved without recursion. Create the half of the template that performs this operation. Then change it, so that it calls itself and performs the operation on the half you have and the result of the call. Now create the half that gets processed when there is nothing left to do. That’s it. You’re done.

Q I’ve seen that all the recursive templates work with one xsl:when and one xsl:otherwise element. Can I have multiple xsl:when elements?

A Sure. You need at least two alternatives, one recursive and one nonrecursive (the escape hatch). You can, of course, also have more of each.

Workshop

This workshop tests whether you understand all the concepts you learned today. It is helpful to know and understand the answers before starting tomorrow’s lesson. You can find the answers to the quiz questions and exercises in Appendix A.

Quiz

1. True or False: You can create recursive templates without parameters.

2. True or False: If there is no “escape hatch,” a recursive function will keep calling itself.

3. Can you do recursion with xsl:apply-templates instead of xsl:call-template?

4. Can a recursive template return a node-set or a tree fragment instead of a simple value?

5. When shouldn’t you use recursion?

Exercises

1. Alter Listing 17.4 so that it generates a result such as Tuco B. P. J. M. Ramirez instead of T. B. P. J. M. Ramirez.

2. Based on Listing 17.3, create a stylesheet that converts

    <name>John Fitzgerald Kennedy</name>

to

    <name>
      <firstname>John</firstname>
      <firstname>Fitzgerald</firstname>
      <lastname>Kennedy</lastname>
    </name>