Subject: Re: [xsl] Show all permutations of N coins ... without using recursion?|
From: David Carlisle <davidc@xxxxxxxxx>
Date: Mon, 02 Sep 2013 10:27:02 +0100
Excellent point David.
Michael Kay, does SAXON implement xsl:iterate using recursion? Does SAXON implement xsl:for-each using recursion?
That's the wrong question:-) If you naively implement recursion as a recursive call then you'd never get streaming capability, but the point is that a tail recursive function can be (and is, usually) rewritten by the complier to essentially turn into a loop (as there is no need to make a stack of all the local state of each function call as the local state is never used after the recursive call (hence the name _tail_ recursion).
For-each is a different kettle of fish, but the point is if you re-write a tail recursive function to use xsl:iterate, it doesn't necessarily make any difference as the compiler can make similar rewrites internally. (Saxon can certainly detect and re-write recursive calls, I don't know if its rewrites are streamable but it is certainly allowed to make them so)