Actually, as I point out in the book, you need to be fairly careful how you
code this if you want to take advantage of tail recursion even in a
processor that offers this optimization. (I don't offer the solution in the
book and I'm not offering it here - there are other things I want to get
done this evening!)
I don't think the classic divide-and-conquer works here, because you can't
process the right-hand half of the sequence independently of the left-hand
half. There may be ways of breaking up the problem, but nothing comes to
mind.
XSLT 2.1 will offer a new construct for this kind of problem. xsl:iterate is
like an xsl:for-each except that each iteration can set parameters to be
used in the next iteration. The final result is delivered by the
xsl:on-completion instruction. Here's the sample code:
<xsl:iterate select="input">
<xsl:param name="total-so-far" select="0"/>
<xsl:variable name="next-total" select="$total-so-far + ."/>
<xsl:next-iteration>
<xsl:with-param name="total-so-far" select="$next-total"/>
</xsl:next-iteration>
<xsl:on-completion select="$next-total"/>
</xsl:iterate>
The primary motivation was that it's easier to compile this for processing
streamed input than the same operation written recursively; but it's also
easier, I think, for people to get their mind around than head-tail
recursion, and it's also less demanding on the optimizer. There's a preview
of the construct (implemented as extensions in the Saxon namespace) in Saxon
9.2.
Regards,
Michael Kay
http://www.saxonica.com/
http://twitter.com/michaelhkay
-----Original Message-----
From: Costello, Roger L. [mailto:costello(_at_)mitre(_dot_)org]
Sent: 11 December 2009 21:39
To: 'xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com'
Subject: [xsl] Using divide-and-conquer recursion to create a
cumulative sequence
Hi Folks,
I wish to convert a sequence of N numbers:
(23, 41, 70, 103, 99, 6)
Into a cumulative sequence, in which each number is the sum
of the previous numbers:
(23, 64, 134, 237, 336, 342)
One approach to solving this is to iterate through the N
numbers and sum the preceding numbers:
for i=1 to N
sum(for j=1 to i return numbers[j])
However, that approach has a time complexity of:
1 + 2 + 3 + ... + N = N**2/2
For large N, that will be very expensive.
An alternative approach is to create a recursive function
that does a single pass through the sequence, carrying along
(and adding) the accumulated total on each recursive call.
This has a time complexity of N. Nice.
*********************************************************************
The above (paraphrases) from Michael Kay's book, XSLT 2.0 and
XPath 2.0, p. 993.
The below is from me.
*********************************************************************
However, that sequential recursive approach will entail N
recursive calls, which will result in running out of memory
for large N (let's assume that the XSLT processor does not do
tail recursive optimization).
I would like a way of solving the problem using
divide-and-conquer recursion. Can you provide a solution?
/Roger
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--