Tail recursion in XML

Recursion as we all have studied is a programming pattern where in we call the same function repeatedly.

or in other words we can say it describe a process of repeating objects in a self-similar way.

And the most famous example for this is factorial of a number.


Factorial of any number is multiple of all the whole numbers less than or equal to the number.

So if i say factorial 4 that means 4*3*2*1=24 is the factorial of 4

So if you have to implement it programatically how we will implement it.It should be something like this.



=================================


public class Recursion{

public static long factorial(double fact)

if (fact==1)

return 1;

else

retrun fact*factorial(fact-1)

}


public static void main(String[] args) {

System.out.println(factorial(3));
}


SO now we will try to understand how it works


We are calling here factorial(3) in our main program

it will go to the definition of factorial

and check if the value given is equal to 1

if not it will go to else block where in it will do

3*factorial(3-1)

that is factorial(2)


so it will go on till the value fact becomes 1

so the total output will be something like this


1st iteration

3*factorial(2)

2nd iteration

2*factorail(1)


so overall result will be

3*2*1=6





Tail recursion is different as it is form of recursion that can be implemented much more efficiently than

general recursion. In general a recursive call requires the compiler to allocate some memory at run-time

for every call that has not yet returned. This memory consumption makes recursion inefficient for

representing repetitive algorithms having large or unbounded size. Tail recursion is the special case of recursion

because it is equivalent to iteration, tail-recursive programs can be compiled as efficiently as

iterative programs.


In this exercise we will just have a look in xsl program that how we can implement a recursion in xsl.

so here is my xsl code for the same

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:template match="factorial" name="factorial">
<xsl:param name="number" select="@number" />
<xsl:param name="f" select="1" />
<xsl:if test="$number &gt; 1">
<xsl:call-template name="factorial">
<xsl:with-param name="number">
<xsl:value-of select="$number - 1" />
</xsl:with-param>
<xsl:with-param name="f">
<xsl:value-of select="$f * $number" />
</xsl:with-param>
</xsl:call-template>
</xsl:if>
<xsl:if test="$number = 1">
<xsl:value-of select="$f" />
</xsl:if>
</xsl:template>
</xsl:stylesheet>


and the corresponding xml document

<?xml version="1.0" encoding="ISO-8859-1"?>
<factorial number = "4"/>


so the result in this case should be 24 as shown below.




Now coming to tail recursion,if we try to implement the same program through tail recursion which is probably
an optimization technique will eliminate the recursion depth.It is based on the fact that storage of state information
will be removed now and all the execution will be done in a single step.I tried to find out document how to do that
but without success,Seeking readers input on the same.

This example will work only for values less than 170 for 171 it will give a value NAN

as this was the limitation in XPATH 1.0

With XPATH 2.0 new data type has been defined so you can use now xs:integer to define your input variable

and get the out put value for big numbers too