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

 Subject: RE: Using divide-and-conquer recursion to create a cumulative sequence From: "Costello, Roger L." Date: Wed, 23 Dec 2009 13:32:21 -0500
```Hi Folks,

On 11 December 2009 I inquired on this list about how to create a recursive,
divide-and-conquer XSLT transform that creates a cumulative sequence (see
below for my original post).

Dimitre Novatchev and Hermann Stamm-Wilbrandt responded with excellent
solutions. Dimitre provided a solution that used XSLT 2.0 and Hermann provided
a solution that used 1.0 plus EXSLT extensions.

I was interested in an XSLT 1.0 solution without using extensions. After
reflecting on Dimitre's and Hermann's solutions, I came up with the below
solution. I believe that it has a time complexity of O(n log2n). If I err in
my complexity calculation, please let me know.

Here is the XSLT:

<xsl:template name="cumulative">
<xsl:param name="numberList" />
<xsl:param name="sum" select="0" />

<xsl:choose>
<xsl:when test="not(\$numberList)" />
<xsl:when test="count(\$numberList) = 1">
<xsl:value-of select="\$numberList + \$sum" />
<xsl:text> </xsl:text>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="mid" select="floor(count(\$numberList) div
2)"/>
<xsl:call-template name="cumulative">
<xsl:with-param name="numberList"
select="\$numberList[position() &lt;= \$mid]"/>
<xsl:with-param name="sum" select="\$sum"/>
</xsl:call-template>
<xsl:call-template name="cumulative">
<xsl:with-param name="numberList"
select="\$numberList[position() &gt; \$mid]"/>
<xsl:with-param name="sum" select="\$sum +
sum(\$numberList[position() &lt;= \$mid])"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:template>

/Roger

-----Original Message-----
From: Costello, Roger L.
Sent: Friday, December 11, 2009 4:39 PM
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

```

### PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!