RE: Using divide-and-conquer recursion to create a cu

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@xxxxxxxxx] 
> Sent: 11 December 2009 21:39
> To: 'xsl-list@xxxxxxxxxxxxxxxxxxxxxx'
> Subject:  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