xsl-list
[Top] [All Lists]

Re: [xsl] Two versions of sum over node list by recursion--why and how does second one work?

2006-09-05 09:14:36

the second is the normal recursive definition of the sum of a list: the
sum function doesn't take a parameter, the result is just returned as
the result of the function.

sum of a list is defined by

sum (empty-list) = 0
sum(list)= 1st-item + sum(rest-of-list)


see, sum() here doesn't need an explict result parameter.
technically though this means that intermediate results get saved in the
processor's function call stack and so if you have too long a list you
run out of stack space.

Such functions (for some definition of "such") can always be written in
tail recursive form where instead the intermediate results are instead
accumulated in a parameter

sum(list)=sum2(list,0)
sum2(empty-list,total)=total
sum2(list,total)=sum2(rest-of-list,1st-item+total)

For Dimitre, it can also be written as a divide and conquer
sum(empty-list)=0
sum(item)=item
sum(list)=sum(even-position-items)+sum(odd-position-items)

David

--~------------------------------------------------------------------
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>
--~--