Re: Maximum recursion depth exceeded

On Tue, Jul 7, 2009 at 1:19 AM, bryan
rasmussen<rasmussen.bryan@xxxxxxxxx> wrote:
> On Tue, Jul 7, 2009 at 9:55 AM, Michael Kay<mike@xxxxxxxxxxxx> wrote:
>>> anyway, recursion problems are likely to be a problem in .NET
>>> / C#, as far as I know currently the only .NET language that
>>> can compile and optimize for tail recursion is F#..
>>
>> Well, I know of at least two others: XSLT and XQuery, as implemented by
>> Saxon.
>>
> I don't think those would be considered as .NET languages, those are
> languages implemented in .NET. Sorry if I was imprecise earlier.
>

1. Quite some of Bryan's statements about how "System.Xml.Xsl" does
work are far from correct. One of them is that tail recursion is not
supported. Tail recursion *is* optimized by XslCompiledTransform in
non-debugging mode.

2. To the original OP: The message by Saxon is generally presented
whenever Saxon runs out of memory -- this may or maynot be caused by
recursion stack overflow!

3. If recursion stack overflow is indeed the cause, then there is a
good and general cure: Use DVC (Divide and Conquer). DVC has a maximum
recursion stack depth of log2(N). For example, to process a sequence
of 1000000 (1M) items, a recursion stack with maximum depth of 19 will
be needed. Thus, using DVC recursion in practice eliminates the
recursion stack-overflow problem.

Whenever a programmer uses DVC recursion he is in full control and not
at the mercy of every optimizer he has the good (or bad) luck of
working with. FXSL comes with most of its important functions ( such
as f:foldl() ) using DVC, so the programmer even does not write his
own DVC.

To summarize: Prefer using DVC recursion to tail-recursion as a
practical way to avoid the recursion stack overflow problem.


-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play