XSLT 2.0 and XPath 2.0 Programmer's Reference, 4th Edition (177 page)

Recursion

Stylesheet functions can be recursive: they can call themselves either directly or indirectly. Because XSLT is a functional programming language without side effects (at any rate, without updateable variables), recursion plays a key role in writing algorithms of any complexity.

In XSLT 1.0, such algorithms were written using recursive named templates. Apart from being rather long-winded, this had the drawback that it was difficult to return certain kinds of result: templates in XSLT 1.0 could only return results by constructing new nodes. In XSLT 2.0 both templates and functions offer much more flexibility in the types of result they can return, and stylesheet functions offer additional flexibility in the way they can be called (for example, they can be called from within a predicate used in a match pattern).

As it happens, many of the simple problems where recursion was needed in XSLT 1.0 can now be solved in other ways, because XPath 2.0 offers a wider range of aggregation functions, and functions such as
tokenize()
to break up a string into its parts. But there are still cases where recursion is needed, and even when it isn't, many people find the recursive solution more elegant than an iterative solution using

or the XPath
for
expression.

Here is a function that extracts the part of a string after the last
/
character:

Note how all the logic is contained in a single XPath expression. I could have used

to express the same logic, but with this kind of function I personally find it clearer to write the whole algorithm at the XPath level.

The function result is returned using an

instruction. It sometimes feels a little strange to use

when the value being computed is a single integer or string, but in the XDM model a single value is the same as a sequence of length 1, so it's worth getting used to the idea that everything is a sequence. When returning an atomic value, one could just as easily use

, but I prefer

because it works in all cases; when you are returning nodes, you don't want to copy them unnecessarily. You might also be tempted to use

, and in this case it would work, but the semantics aren't quite what we want:

would convert the selected string into a text node, which would then be atomized back to a string by virtue of the function's declared return type. Even if the optimizer can sort this out, it's making unnecessary work.

Another observation about this function is that it is tail-recursive. This means that after calling itself, the function does nothing else before it returns to its caller. This property is important because tail-recursive functions can be optimized to save memory. Sometimes a problem with recursion is that if you recurse too deeply, say to 1000 levels or so, the system runs out of stack space and terminates with a fatal error. A good XSLT processor can optimize a tail-recursive function so that this doesn't happen. Basically the trick is that instead of making the recursive call and then unwinding the stack when it regains control, the function can unwind the stack first, and then make the recursive call. This is because the stack frame isn't needed once the recursive call returns.

I mentioned earlier that many functions can now be implemented easily without using recursion, and this one is no exception. It could also be written using regular expressions:

But this is a matter of personal style. It's a good idea to have more than one tool in your kitbag, and recursion is the most powerful one available.

One kind of problem where you will need recursion is when you need to analyze a graph (that is, a network of related objects). The next example shows the technique.