Javascript recursion limit

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

Jeff Bigham <jeffrey.bigham (AT) gmail (DOT) com> writes:

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 (AT) hotpop (DOT) com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

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....2a3100608da41e
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.

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

On May 17, 6:28 pm, Thomas 'PointedEars' Lahn <PointedE... (AT) web (DOT) 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....4a715c35212576

Thomas 'PointedEars' Lahn <PointedEars (AT) web (DOT) de> writes:

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 (AT) hotpop (DOT) com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

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

On May 17, 7:37 pm, Lasse Reichstein Nielsen <l... (AT) hotpop (DOT) com> wrote:

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.

Thomas 'PointedEars' Lahn <PointedEars (AT) web (DOT) de> writes:

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 misunderstandings 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 (AT) hotpop (DOT) com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

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 bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16