Re: Recursion performance (fibonacci numbers)

Dimitre asked a similar question a while back:

http://www.xslt.com/html/xsl-list/2005-06/msg00844.html

at least, the first part of his question involved calculating fibonacci
numbers efficiently. I'm not sure he ever published the results that
people sent him.

For fibonacci, I suggested:

<xsl:function name="x:fib" as="xs:integer">
 <xsl:param name="n" as="xs:integer"/>
 <xsl:choose>
 <xsl:when test="$n=0">
  <xsl:sequence select="1"/>
 </xsl:when>
 <xsl:when test="$n =1">
  <xsl:sequence select="1"/>
 </xsl:when>
 <xsl:when test="$n mod 2 = 0">
  <xsl:variable name="n2" select="$n idiv 2"/>
  <xsl:variable name="fn" select="x:fib($n2)"/>
  <xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
 <xsl:sequence select="$fn * $fn + $fn-1 * $fn-1"/>
 </xsl:when>
 <xsl:when test="$n mod 2 = 1">
  <xsl:variable name="n2" select="($n - 1) idiv 2"/>
  <xsl:variable name="fn" select="x:fib($n2)"/>
  <xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
 <xsl:sequence select="(2 * $fn-1 + $fn) * $fn"/>
 </xsl:when>
</xsl:choose>
</xsl:function>

which should I think me considerably quicker than the function that you
suggested for large numbers.


David


________________________________________________________________________
This e-mail has been scanned for all viruses by Star. The
service is powered by MessageLabs. For more information on a proactive
anti-virus service working around the clock, around the globe, visit:
http://www.star.net.uk
________________________________________________________________________