[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: What is the Maximum number of recurssions

Subject: Re: What is the Maximum number of recurssions
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Thu, 1 Mar 2012 13:23:03 -0800
Re:  What is the Maximum number of recurssions
On Thu, Mar 1, 2012 at 12:36 PM, Karl Stubsjoen <kstubs@xxxxxxxxx> wrote:
> I'm just curious, what is the maximum number of times a template can
> recurse?

I guess you men the number of nested recursive calls (nestedness).
There is no fixed maximum and in some cases a correctly written
template/function can have nestedness measured in the millions.

Such are the cases with tail-recursive functions/templates -- and this
requires that the XSLT processor can recognize and optimize tail
recursion.

For example, this transformation run with Saxon 6.5.4 successfully
prints all numbers from 1 to one million:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:call-template name="printToN"/>
 </xsl:template>

 <xsl:template name="printToN">
  <xsl:param name="pUpTo" select="1000000"/>
  <xsl:param name="pDoneWith" select="0"/>

  <xsl:if test="$pUpTo > $pDoneWith">
   <xsl:value-of select="$pDoneWith+1"/>
   <xsl:text>&#xA;</xsl:text>

   <xsl:call-template name="printToN">
    <xsl:with-param name="pUpTo" select="$pUpTo"/>
    <xsl:with-param name="pDoneWith" select="$pDoneWith+1"/>
   </xsl:call-template>
  </xsl:if>
 </xsl:template>
</xsl:stylesheet>

However, other XSLT processors (AltovaXML) produce this error: "XSLT
instruction stack overflow"

A DVC (Divide and Conquer) style recursion is also a practical
solution and processing a sequence of N items requires a maximum
nestedness of only log(N). This recursive style is remarkable in that
it doesn't require (as required in the case of tail recursion) any
special abilities from the XSLT processor and works correctly with any
XSLT processor. Thus the maximum callstack depth when processing a
sequence of one million items with DVC-style recursion, is only 19.

> I would imagine it would be different from engine to engine.
> B Is there any other engine intelligence at play here, for example the
> engine has decided that you've written and endless looping recursion,
> instead of one that knows you'll eventually reach the end of your
> source xml?


This is generally impossible to do, because whether or not an
algorithm finishes often depends on the specific data that is fed to
it -- typical examples are many numerical methods that converge only
if the data is limited in a specific interval or by any other
condition.

Cheers,
Dimitre.

>
> Thanks,
> Karl..
>
> --
> Karl Stubsjoen
> MeetScoresOnline.com
> (602) 845-0006
>



--
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
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.