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