Javascript recursion limit

[Jeff Bigham]

So, it appears that Javascript has a recursion limit of about 1000
levels on FF, maybe less/more on other browsers.

Should such deep recursion then generally be avoided in Javascript?
Surprisingly, deep recursion actually isn't that slow for what I'm
doing. Programming this task recursively is so much more
straightforward to me, but currently I'm forced to use an ugly hack to
avoid going over the 1000 level limit. Of course, it could just break
if it's lower in another browser, so it's not ideal.

Is recursion not a viable option in Javascript?

Thanks,
Jeff

[Lasse Reichstein Nielsen]

Re: Javascript recursion limit

Jeff Bigham <jeffrey.bigham @gmail.comwrite s:

So, it appears that Javascript has a recursion limit of about 1000
levels on FF, maybe less/more on other browsers.

That *implementation * might have a limited stack space. The language
itself does not require such a limit.

Should such deep recursion then generally be avoided in Javascript?

Apparently, if you want it to work in Firefox. You seem to have already
answered that yourself, or am I missing something?

Surprisingly, deep recursion actually isn't that slow for what I'm
doing.

Recursion doesn't need to be slow, so I don't find that surprising.

Programming this task recursively is so much more
straightforward to me, but currently I'm forced to use an ugly hack to
avoid going over the 1000 level limit.

The limit might be a hard limit on the number of nested method calls
(some people appears to think that deep recursion must be a mistake),
or it might be an implicit limit given by the stack size of the
runtime environment (i.e., if you pass more parameters, then the limit
will be lower).

Of course, it could just break if it's lower in another browser, so
it's not ideal.

True. That is a problem with using deep recursion in any language.
Most languages have a stack that can't grow unlimited, and each
recursive call requires the storing of some information (at least
the return address).

Is recursion not a viable option in Javascript?

As viable as in any other *language* - i.e., limited by the implementation
and/or platform that it runs under.
Javascript in web pages just has the extra problem that the author doesn't
get to pick the language implementation.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[VK]

Re: Javascript recursion limit

So, it appears that Javascript has a recursion limit of about 1000

levels on FF, maybe less/more on other browsers.

It is hard to say universally. As already pointed out, ECMAScript
specs do not put any specific restrictions of the kind, so it is a per-
engine feature.

The original Netscape's JavaScript engine, used with modifications in
Netscape 2.x - Netscape 4.x had the following build-in limits:

Quoting by Brendan Eich:
"No more than 2^20 symbols among all scopes. No more than 2^16 atoms
(identifiers, numeric literals, string literals) referred to by source
loaded at any instant into one context (window). There are no other
static limits in the platform-independent part of the JS
implementation. And the dynamic limit on runtime: 1e6 control flow
transfers between "Length JavaScript running. Continue?" dialog
boxes."

See also:

http://groups.google.com/group/comp.lang.javascript/msg/7b2a3100608da41e

and

http://jsnet.sourceforge.net/tmp/clj_1996.htm

I do not know what engines - if any - may be still using this as a
guideline.

Should such deep recursion then generally be avoided in Javascript?

Stack overflow attacks are the most used by hackers and respectively
the stack control is the primary watch-out of engines' developers -
and not for Javascript only. I would say this way: there is nothing
wrong with recursions as a programming approach by itself. At the same
time a nice theoretical construction may get hardly usable after being
brought into alas imperfect real world: where are still plenty of
idiots trying to infect their visitors or at least freeze their
browsers so forcing them to close the application as the only way to
leave the site. So I would keep recursions as a theoretical construct
one needs to learn to get their diploma: but I would avoid using them
for any programming where the target environment is not known in
advance. Otherwise you never can be sure that the same recursion block
will work for everyone - or it may stop working suddenly after next
security fix or upgrade.

[Thomas 'PointedEars' Lahn]

Re: Javascript recursion limit

Jeff Bigham wrote:

So, it appears that Javascript has a recursion limit of about 1000 levels
on FF, maybe less/more on other browsers.

Your analysis is superficial at best. You don't even know what you are
talking about to begin with: There is no "Javascript ". There are
JavaScript, JScript, and other ECMAScript implementations .

Should such deep recursion then generally be avoided in Javascript?

How many recursions are allowed depends on the stack size limit, and on the
size of the symbols that have to be put on the stack on each recursion.
That fact is no different from other programming languages. However, known
ECMAScript implementations use a Virtual Machine to interpret byte-code
compiled from source code, so the stack size limit is that of this VM
instead and may therefore differ between different VMs running on the same
machine.

Surprisingly, deep recursion actually isn't that slow for what I'm doing.

Your surprise is completely unfounded.

Programming this task recursively is so much more straightforward to me,
but currently I'm forced to use an ugly hack to avoid going over the 1000
level limit.

I don't think so. Every recursion can be rewritten into an iteration, no?

Is recursion not a viable option in Javascript?

Wrong question.


PointedEars
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrmann

[VK]

Re: Javascript recursion limit

On May 17, 6:28 pm, Thomas 'PointedEars' Lahn <PointedE...@we b.de>
wrote:

You don't even know what you are
talking about to begin with: There is no "Javascript ". There are
JavaScript, JScript, and other ECMAScript implementations .

By your own strictly personal opinion not shared by anyone else here.
You can have any opinions you like, but please don't represent them as
"everyone knows it" .

http://groups.google.com/group/comp.lang.javascript/browse_frm/thread/aef39a1c424ef2fb/544a715c35212576?#544a715c35212576

[Lasse Reichstein Nielsen]

Re: Javascript recursion limit

Thomas 'PointedEars' Lahn <PointedEars@we b.dewrites:

I don't think so. Every recursion can be rewritten into an iteration, no?

It can, just as any iteration can be rewritten into recursion.
For some problems, the recursive specification is much more direct and
straightforward .

Recursion is effectively using the call stack as a data structure. If
you unroll the iteration, you'll just have to implement the stack in
another way (unless the algorithm doesn't really need the recursion).
That might work better, since heap memory is often less limited than
stack memory.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Thomas 'PointedEars' Lahn]

Re: Javascript recursion limit

VK wrote:

[...] Thomas 'PointedEars' Lahn [...] wrote:

>You don't even know what you are
>talking about to begin with: There is no "Javascript ". There are
>JavaScript, JScript, and other ECMAScript implementations .

>
By your own strictly personal opinion not shared by anyone else here.

That is not an opinion, it is a fact accepted by people who know what
they are talking about (not you, of course). There have been a number
of misunderstandin gs regarding this in the past, nevertheless it is true.
It is even more important regarding the question at hand, as different
implementations may exhibit different stack sizes and stack usage just
because they are different.

http://PointedEars.de/es-matrix

PointedEars
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrmann

[VK]

Re: Javascript recursion limit

On May 17, 7:37 pm, Lasse Reichstein Nielsen <l...@hotpop.co mwrote:

For some problems, the recursive specification is much more
direct and straightforward .

For reasons spelled in my first post I dropped iterations by the end
of 1998 - when it became a subject of security considerations and
respectively endless fixes and limitations.

I just run a quick check on available browsers to see what the
industry had came to in ten years. As a reminder the starting point
was the idealistic 1,000,000 - a reasonable number for a reasonable
yet not existing word. The results are impressive:

Firefox 2.0.0.14 - 1000 iterations limit
Internet Explorer 6.0 - 1124 iterations limit
Opera 9.27 - 3339 iterations limit
Safari 3.0.4 - 499 iterations limit (wow!)

Also each tested engine has intellectual "interface freezing attempt"
sniffing, so straightforward for-in loops with iterations will be
never executed event for 10 iterations: the engine will raise "too
many recursions" error before event trying to execute the code. if-
looping with manual counter is still allowed - but for how long. So I
stay with my original opinion: the programming idea of iterations was
good, but as a practical coding approach it is pretty much dead tool:
thanks to legions of bored idiots around the glob trying to do bad to
other people.

[Lasse Reichstein Nielsen]

Re: Javascript recursion limit

Thomas 'PointedEars' Lahn <PointedEars@we b.dewrites:

VK wrote:

>[...] Thomas 'PointedEars' Lahn [...] wrote:

>>You don't even know what you are
>>talking about to begin with: There is no "Javascript ". There are
>>JavaScript, JScript, and other ECMAScript implementations .

>>
>By your own strictly personal opinion not shared by anyone else here.

>
That is not an opinion, it is a fact accepted by people who know what
they are talking about (not you, of course).

Facts does not define how language works. People do.
I am fully aware of the number of different implementation of languages
that are (more or less) ECMAScript compliant, and runtime environments
that are (more or less) W3C DOM compliant.

If a script element with type="text/javascript" is encountered by
a browser, it uses its own ECMAScript-like language implementation
to parse it.
That does not mean that the content of the script element is JScript
when IE interprets it and JavaScript when Mozilla interprets it.
The content doesn't change, only its interpretation. Rarely will
the author have written the content to target a specific ECMAScript
compatible language.

The language that most people do write in those script elements has
no name or formal definition. It is closer to the intersection of
the languages implemented by the targeted clients (or, with feature
detection and switching, the union of the languages).

Because people likes things to have a name, the obvious name to apply
to it is "javascript ". And that is what everybody else have been
doing, consistently, for as long as it has mattered (q.v. the name of
this group).

I.e., it's *common usage*. Not formal definition, not official standard,
but still quite valid.

If anybody want this use of the word "javascript " to go away, they
need to come up with a better name. Anything else is flailing at
windmills.

There have been a number of misunderstandin gs regarding this in the
past, nevertheless it is true.

No, it's not. There is a "javascript ". There is, by and large, consensus
about what it means. No lack of formal standard can change that. That's
just not how human languages work.

It is even more important regarding the question at hand, as
different implementations may exhibit different stack sizes and
stack usage just because they are different.

Implementation matters, obviously, especially with anything that isn't
part of any standard (e.g., memory limits). I also doubt there is any
current language implementation that is 100% compliant with the
ECMAScript 3rd edition standard.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Thomas 'PointedEars' Lahn]

Re: Javascript recursion limit

VK wrote:

Firefox 2.0.0.14 - 1000 iterations limit

As I said, such an analysis is superficial at best:

for (var i = 1; i < n; i++) ;

causes a warning when n == 1000000 because of my Firefox's
"dom.max_script _run_time" preference set to 1800 (for testing purposes).

And if you meant recursions instead of iterations,

(function f(x)
{
console.log(x);
f(x + 1);
})(0);

stops with a stack overflow after logging 994.

Tested in Firebug 1.1.0b12, Firefox 2.0.0.14.


PointedEars
--
var bugRiddenCrashP ronePieceOfJunk = (
navigator.userA gent.indexOf('M SIE 5') != -1
&& navigator.userA gent.indexOf('M ac') != -1
) // Plone, register_functi on.js:16

[Thomas 'PointedEars' Lahn]

Re: Javascript recursion limit

Lasse Reichstein Nielsen wrote:

Because people likes things to have a name, the obvious name to apply
to it is "javascript ". And that is what everybody else have been
doing, consistently, for as long as it has mattered (q.v. the name of
this group).
>
I.e., it's *common usage*. Not formal definition, not official standard,
but still quite valid.

When "common usage" proves insufficient to explain certain phenomena, it
should be replaced by more precise terms, especially in a discussion in a
technical environment.


PointedEars
--
var bugRiddenCrashP ronePieceOfJunk = (
navigator.userA gent.indexOf('M SIE 5') != -1
&& navigator.userA gent.indexOf('M ac') != -1
) // Plone, register_functi on.js:16

[Thomas 'PointedEars' Lahn]

Re: Javascript recursion limit

Thomas 'PointedEars' Lahn wrote:

VK wrote:

>Firefox 2.0.0.14 - 1000 iterations limit

>
As I said, such an analysis is superficial at best:
>
for (var i = 1; i < n; i++) ;
>
causes a warning when n == 1000000 because of my Firefox's
"dom.max_script _run_time" preference set to 1800 (for testing purposes).

I should have mentioned that there is no warning if n == 100000, then.
But this is not a matter of iterations, but of the run time required for
them which may differ greatly between execution environments.


PointedEars
--
Use any version of Microsoft Frontpage to create your site.
(This won't prevent people from viewing your source, but no one
will want to steal it.)
-- from <http://www.vortex-webdesign.com/help/hidesource.htm>

[VK]

Re: Javascript recursion limit

On May 17, 8:49 pm, Thomas 'PointedEars' Lahn <PointedE...@we b.de>
wrote:

Lasse Reichstein Nielsen wrote:

Because people likes things to have a name, the obvious name to apply
to it is "javascript ". And that is what everybody else have been
doing, consistently, for as long as it has mattered (q.v. the name of
this group).

>

I.e., it's *common usage*. Not formal definition, not official standard,
but still quite valid.

>
When "common usage" proves insufficient to explain certain phenomena, it
should be replaced by more precise terms, especially in a discussion in a
technical environment.

Like what?

- I am writing JavaScript1.5 program for Firefox, I am writing
JavaScript1.7 program for Firefox, I am writing JScript program for
IE6, I am writing JScript program for IE7, I am learning ECMAScript
and shall be blessed all other names which are not here. Amen!
.... this line gives me an error: document.write( "John "Bool" Smith");
Why?

- Your JavaScript1.5 program for Firefox, your JavaScript1.7 program
for Firefox, your JScript program for IE6, your JScript program for
IE7, your ECMAScript and shall be blessed all other names which are
not here. Amen!
.... doesn't work because it has nested quotes of the same type. Either
replace outer quotes by single ones, or escape inner ones:
document.write( 'John "Bool" Smith');
document.write( "John \"Bool\" Smith");

Are you really insisting on such dialogs at c.l.j.? :-)

There is JavaScript in many variants, there is JScript in many
variants, there is also ActionScript and God knows what else. If the
problem is particular to a specific engine or/and OS it will be
mentioned. Otherwise this group talks about "javascript " or
"Javascript " and sapienti sat.

P.S. Why are you always choosing the most rediculous subject to have a
stand?

[Thomas 'PointedEars' Lahn]

Re: Javascript recursion limit

VK wrote:

On May 17, 8:49 pm, Thomas 'PointedEars' Lahn <PointedE...@we b.de>
wrote:

>Lasse Reichstein Nielsen wrote:

>>Because people likes things to have a name, the obvious name to apply
>>to it is "javascript ". And that is what everybody else have been
>>doing, consistently, for as long as it has mattered (q.v. the name of
>>this group).
>>I.e., it's *common usage*. Not formal definition, not official standard,
>>but still quite valid.

>When "common usage" proves insufficient to explain certain phenomena, it
>should be replaced by more precise terms, especially in a discussion in a
>technical environment.

>
Like what?
>
- I am writing JavaScript1.5 program for Firefox, I am writing
JavaScript1.7 program for Firefox, I am writing JScript program for
IE6, I am writing JScript program for IE7, I am learning ECMAScript
and shall be blessed all other names which are not here. Amen!
... this line gives me an error: document.write( "John "Bool" Smith");
Why?
>
- Your JavaScript1.5 program for Firefox, your JavaScript1.7 program
for Firefox, your JScript program for IE6, your JScript program for
IE7, your ECMAScript and shall be blessed all other names which are
not here. Amen!
... doesn't work because it has nested quotes of the same type. Either
replace outer quotes by single ones, or escape inner ones:
document.write( 'John "Bool" Smith');
document.write( "John \"Bool\" Smith");
>
Are you really insisting on such dialogs at c.l.j.? :-)

http://en.wikipedia.org/wiki/Appeal_to_ridicule

There is JavaScript in many variants,

No. There is only one Netscape/Mozilla.org JavaScript, and different
versions of it, all implemented in Mozilla browsers.

there is JScript in many variants,

No. There is only one (Microsoft) JScript, and different versions of it,
all implemented in Microsoft software.

there is also ActionScript

Yes. However, it seldom matters regarding browser scripting as it is
restricted to the Adobe Flash runtime environment.


PointedEars
--
Use any version of Microsoft Frontpage to create your site.
(This won't prevent people from viewing your source, but no one
will want to steal it.)
-- from <http://www.vortex-webdesign.com/help/hidesource.htm>

[Thomas 'PointedEars' Lahn]

Re: Javascript recursion limit

VK wrote:

>>Firefox 2.0.0.14 - 1000 iterations limit

>And if you meant recursions instead of iterations,

>
Well, we are changing the amount of iterations to check the allowed
limit of recursions :-)

You are not making sense.

but you are right with the correction.
>

> (function f(x)
> {
> console.log(x);
> f(x + 1);
> })(0);
>>
>stops with a stack overflow after logging 994.
>>
>Tested in Firebug 1.1.0b12, Firefox 2.0.0.14.

>
You are missing 6 recursions because
1) 2 are used even before going to the loop:

There is no loop.

for anonymous function wrapper ()() and for f() inside it.

No, it is the same number if I use

function f(x)
{
console.log(x);
f(x + 1);
}

f(0);

2) The rest is used for anonymous wrappers for your code in Firebug.
[...]

It is the same number when using

javascript: function f(x) { console.log(x); f(x + 1); } f(0);

in the Location Bar. With

javascript: document.open() ; function f(x) { document.write( x + "<br>");
f(x + 1); } f(0); document.close( );

it is 999, not 1000.

Drop Firebug and use this instead:
Again, 999 because one stack position is already used for the entry
point.

A recursion does not occur until the method calls itself. So it is 999
recursions, if that.

Change to 1000 to break the script.

I am not changing anything; your test is flawed (and includes a lot of
unnecessary code again). It should count forwards, not backwards.


PointedEars
--
Prototype.js was written by people who don't know javascript for people
who don't know javascript. People who don't know javascript are not
the best source of advice on designing systems that use javascript.
-- Richard Cornford, cljs, <f806at$ail$1$8 300dec7@news.de mon.co.uk>