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]

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

 

[VK]

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]

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

 

[VK]

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...1c424ef2fb/544a715c35212576?#544a715c35212576

 

[Lasse Reichstein Nielsen]

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

 

[Thomas 'PointedEars' Lahn]

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

 

[VK]

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]

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

 

[Thomas 'PointedEars' Lahn]

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

 

[Thomas 'PointedEars' Lahn]

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

 

[Thomas 'PointedEars' Lahn]

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

 

[VK]

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?

 

[VK]

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).

That is completely different issue - with overall time allowed a
single script to run w/o stops. But you already mentioned it in the
next post.

And if you meant recursions instead of iterations,

Well, we are changing the amount of iterations to check the allowed
limit of recursions 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: for anonymous function
wrapper ()() and for f() inside it.
2) The rest is used for anonymous wrappers for your code in Firebug.
It uses them to trap errors from probes. This is why by the way I am
not so crazy at all about Firebug and similar top-level debugger add-
ons. They are inevitably adding too much of "tester effect" into
results, other words the program used to study other program affects
the subject's of study behavior. A real debugger has to run on system
level and to report what is really going on and not what the subject's
of study decides to tell. In this aspect IE's Script Debugger, however
old and limited it is, IMO bits Firebug for reliability of results.

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

test1 is to demonstrate build-in protection for potentially malicious
code. comment test2 and uncomment test1 to check it.


<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html>
<head>
<meta http-equiv="Content-type"
content="text/html; charset=iso-8859-1">
<title>Demo</title>
<script type="text/javascript">

var out = null;

var counter1 = 0;

var counter2 = 999;

function test1() {
for (counter1; counter1<10; counter1++) {
try {
test1();
}
catch(e) {
out.value+= counter1 + ' ' + e.message + '\n';
}
}
}

function test2() {
if (counter2>0) {
counter2--;
test2();
}
else {
out.value = 'OK';
}
}

function init() {
out = document.forms[0].elements['out'];
//test1();
test2();
}

window.onload = init;
</script>
</head>
<body>
<form action="" onsubmit="return false;">
<fieldset>
<legend>Test</legend>
<textarea name="out" rows="16" cols="64"></textarea>
</fieldset>
</form>
</body>
</html>

 

[Thomas 'PointedEars' Lahn]

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

 

[Thomas 'PointedEars' Lahn]

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.


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

 

[VK]

You are not making sense.



There is no loop.

Look closer.

No, it is the same number if I use

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

f(0);

because there are still two stack position used: for f(0) call and for
f(x) for the initial enter. The only difference from the first option
is that here the first stack position is taken by a named function and
in the first example - by an anonymous function. Sorry, but you really
should refresh the stack mechanics theory during this week-end.

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.

Same explanation, same suggestion to you. You simply cannot start
executing a function without executing it at least once. This is why
for top level tests you have to add 1 to the result. The only other
option is to watch the stack size itself on the system level.

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

Recursion starts then you call a function, because it still requires a
return point to store. Even such everyday trivia like
myFunction(args);
is in fact a "micro recursion" one level deep with the return point
set to the code immediately following the function call.

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

So change it as you like. I used this script to find the maximum, not
minimum, so it was more convenient to me to change max values and
count to zero. Just rebuild the loop to go to the opposite side.

 

[Thomas 'PointedEars' Lahn]

Care to explain yourself?

Look closer.

There still is no loop. A loop would mean iteration, this is recursion.
This is the second time in a row you confuse the two, I suggest you look
them up.

because there are still two stack position used: for f(0) call and for
f(x) for the initial enter.

You have argued that the anonymous function wrapper would introduce one
recursion; I have disproved that.

The only difference from the first option is that here the first stack
position is taken by a named function and in the first example - by an
anonymous function. Sorry, but you really should refresh the stack
mechanics theory during this week-end.

Pot, cattle, black.

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.

Same explanation, same suggestion to you.

Same old idiot.

You simply cannot start executing a function without executing it at
least once. This is why for top level tests you have to add 1 to the
result.

No, I don't. There are 999 recursions possible, if that, not 1000.

option is to watch the stack size itself on the system level.

The stack size never yields the number of recursions.

Recursion starts then you call a function, because it still requires a
return point to store. Even such everyday trivia like myFunction(args);
is in fact a "micro recursion" one level deep with the return point set
to the code immediately following the function call.

Whatever the definitions in that parallel universe you must live in, in this
universe in the strict sense a recursion is defined as a function calling
itself. So there is no recursion until that happens.

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


PointedEars

 

[VK]

You simply cannot start
executing a function without executing it at least once. This is why
for top level tests you have to add 1 to the result. The only other
option is to watch the stack size itself on the system level.

Correcting myself: it just came to me that eval() execution goes out
of context so doesn't take an extra return point. So here the real
stack depth test for Gecko - removing eval takes extra stack position
so breaking the code:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html>
<head>
<meta http-equiv="Content-type"
content="text/html; charset=iso-8859-1">
<title>Demo</title>
<script type="text/javascript">

var f = new Array(1000);

function init() {
for (var i=0; i<f.length; i++) {
f = new Function('f[' + (i+1) + ']();');
}
f[999] = new Function('window.alert(\'OK\');');
eval('f[0]()');
}

function releaseContextAndInit() {
window.setTimeout('init()',10);
}
window.onload = releaseContextAndInit;
</script>
</head>
<body>
<p>No content</p>
</body>
</html>

 

[VK]

You are missing 6 recursions because 1) 2 are used even before going

There still is no loop.

Yet even more closer than

A loop would mean iteration, this is recursion.

Ah, OK, I see your problem now. The function f calls itself over and
over again until all allowed resources are used - it is an endless
loop. The "loop" term is not exclusively attached neither to
iterations nor to recursions.

You have argued that the anonymous function wrapper would introduce one
recursion; I have disproved that.

where? not in this thread at least.

Pot, cattle, black.

Is it a new vernacular form of "yes, of course"? Simply "OK" would be
enough though...

No, I don't. There are 999 recursions possible, if that, not 1000.

Just use the second test I have just posted. And if you want to add
something useful to the discussion, I would suggest to play with
function f() {}
against of
var f = function() {}
in stack measurement.
I bet it will be a lot of interesting here for people learning the
language by specs instead of by actual implementations. I may make my
test some later if I have time.