RE: [xsl] Fibonacci & XSL

["Michael Kay" <michael.h.kay@xxxxxxxxxxxx>]

You can do it in Saxon 7.x as:

<xsl:function name="m:fibonacci" saxon:memo-function="yes">
<xsl:param name="n" as="xs:integer">
<xsl:result as="xs:integer" 
   select="if ($n=0) then 0
           else if ($n=1) then 1
           else m:fibonacci($n-1) + m:fibonacci($n-2)"/>
</xsl:function>

In XSLT 1.0 you can do by calling a recursive template starting with the
value 0,
calling itself with the value $param+1 until the required parameter
value is reached, each time supplying the values of the last two items
in the sequence as parameters.

Michael Kay
Software AG
home: Michael.H.Kay@xxxxxxxxxxxx
work: Michael.Kay@xxxxxxxxxxxxxx 



> -----Original Message-----
> From: owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx 
> [mailto:owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx] On Behalf Of 
> Kasper Nielsen
> Sent: 17 December 2002 11:19
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: [xsl] Fibonacci & XSL
> 
> 
> This is actually more a question of dynamic programming in 
> XSL. If you can't remember the function it is:
> 
> F0 = 0
> F1 = 1
> f(n)=f(n-1)+f(n-2) for n>=2
> 
> is it possible to make a template that calculates this in 
> linear time (I know it can be done in O(lg n) but linear is 
> enogh) in xsl? The straightforward recursive method for 
> calculating f(n) is clearly exponential in n.
> 
> If it is possible I would prefer an example using memoization 
> because I need it to a similar problem I have.
> 
> regards
>   Kasper
> 
> 
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
> 
> 


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list