[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Using divide-and-conquer recursion to create a cumulat
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! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|