Tuesday, October 16, 2007

Recursively recursing xsl

If you have ever programmed in XSLT you will have come across the problem of not being able to reassign variable values. XSLT is declarative in nature when it comes to variables. In the sense, you can assign a variable once and then the variable is immutable. To get around that you can write recursive functions that do the math for you by returning the desired result in steps. Such functions are pretty darn solid and work well once written, since variables inside them are immutable. Here's an example


Evaluate the sum of the prices in this xml using any one of these XLSTs. Various recursive logic can be employed.

Recursively add each price by selecting one price at a time:

This logic is pretty simple. Here is how it works
  • Get first price
  • Get second price + first price
  • Get third price + second price + first price
and so on until the total count of prices are reached. In this case it is 5. The terminating condition is to return the last price instead of making a recursive call again

Recursively manipulate a node list.
Add the first price to a recursive result each time:

With this logic you begin with a node list of 5
Products. This is what happens
  • Get price of first product
  • Reduce node list size by moving to the next product
  • The Node list size is now 4. First product has been removed
  • Result = Price of first product + Recursively call the same method
  • Get price of first product (which used to be the second product in first iteration)
  • Reduce node list size by moving to the next product
  • The Node list size is now 4. First product has been removed
  • Result = Price of first product(1st Iter) + Price of first product(2nd Iter) + Recursively call the same method
and so on... The terminating condition is to check for the existence of any nodes in the product list. If there are none return 0. So the addition becomes product1+ product2 +... +product5 +0 You should prefer tail recursion where possible since optimizers can execute them in iterations. More on tail recursions here


You can also use the element where applicable. The trick is to know where to use recursion and where not to. For example factorials are not such a bad example of recursion. With factorials you return values like this

if last number
return number;
return number * fac(number-1);

This is ok. The method call stack is proportional to the number of numbers to find the factorial for. That is 5! requires 5 method calls on the call stack.

Method stack:
  • 5 * 4!
  • 4 * 3!
  • 3 * 2!
  • 2 * 1!
  • 1
This becomes a bad idea with fibonacci. Here is some logic to do fibonacci math in recursion

if number <= 1 return 1; else return fibo(number-1) + fibo (number-2); If I want to find the 4th fibonacci number, this is how the logic divides it

Method stack:

  • 4 -> fibo (3) + fibo(2)
  • 3 -> fibo(2) + fibo(1)
  • 2 -> fibo(1) + fibo(0)
  • 1-> 1
  • 0 -> 1

Thats a lotta calls. 8 in total. This logic tries to divide each number into an addition of 1s of that same number. That is -> 3 = 1 + 1 + 1. A large number will take forever to calculate using this logic. It is better to not use recursion for cases like this. You also dont want recursion or XSLT to do too much processing if the browser is going to to the work of translating the stuff into HTML for you.

For more advanced topics on recursion you might want to look at this link


No comments: