Javascript recursion limit
Jeff Bigham
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
--
Lasse Reichstein Nielsen - l...@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
VK
> 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
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrmann
VK
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
> 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.
Thomas 'PointedEars' Lahn
> [...] 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
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
> 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.
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
--
var bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16
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.
Thomas 'PointedEars' Lahn
> 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
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?
VK
>
> 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
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.
Thomas 'PointedEars' Lahn
>>> Firefox 2.0.0.14 - 1000 iterations limit
>
> 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$8300...@news.demon.co.uk>
VK
wrote:
> 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.
Look closer.
> > 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);
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.
> > 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.
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.
> > 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.
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
> On May 17, 11:44 pm, Thomas 'PointedEars' Lahn <PointedE...@web.de>
> wrote:
>> 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.
Care to explain yourself?
>>> 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.
>
> 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.
>>> 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);
>
> 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.
>>> 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.
>
> 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
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[i] = 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
> >>> to the loop:
> >> There is no loop.
>
> > Look closer.
>
> 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.
> > 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.
Is it a new vernacular form of "yes, of course"? Simply "OK" would be
enough though...
> > 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.
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.
Thomas 'PointedEars' Lahn
>>>>> You are missing 6 recursions because 1) 2 are used even before going
>>>>> to the loop:
>>>> There is no loop.
>>> Look closer.
>> There still is no loop.
>
> Yet even more closer than :-)
This is gibberish again.
>> 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 are mistaken. When a function calls itself, i.e. recursion occurs, that
is _not_ considered a loop. A loop is something that closes back on itself.
To make it easier for you to understand the difference, a loop (i.e.
iteration) looks as follows:
* n
,---->----.
| |
-->o |---
^ |
`----<----'
The execution context remains the same with each loop.
Recursion, on the other hand, looks like this:
-->o-----------------
^
|
v
o
^
|
v
o
.
.
.
In ECMAScript terms: While the called object remains the same, the execution
context does not.
A recursive algorithm does not *close back* *on* itself, it *calls forward*
*to* itself. Hence the requirement of a stack for recursion, but not for
iteration.
>> You have argued that the anonymous function wrapper would introduce one
>> recursion; I have disproved that.
>
> where? not in this thread at least.
It had been clear before that you don't know what you are writing *about*;
now it is also clear that you don't know what you are *writing*:
,-<news:28c0a47e-fa22-4b25...@i76g2000hsf.googlegroups.com>
|
| 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.
> [snipped further nonsense]
Lasse Reichstein Nielsen
> You are mistaken. When a function calls itself, i.e. recursion occurs, that
> is _not_ considered a loop.
That depends.
> A loop is something that closes back on itself.
I.e., a loop is something that repeats - that comes back to the
same state, in some sense (not the exact same state, since that would
cause an infinite loop, but the same state wrt. control flow).
An recursive function can do that, if the language allows it.
In languages with proper tail recursion, a recursive function is the
way to create loops. E.g.,
fun sum nil acc = 0
| sum (x::xs) acc = sum xs (acc+x)
> In ECMAScript terms: While the called object remains the same, the execution
> context does not.
True. ECMAScript does not require an implementation to have tail recursion,
and even then, not all recursion is tail recursion.
VK
wrote:
> A recursive algorithm does not *close back* *on* itself, it *calls forward*
> *to* itself. Hence the requirement of a stack for recursion, but not for
> iteration.
OK, let's us set the grounds first: iterations, recursions, finite
loops, infinite loops etc. these are all top level mental constructs
used in the programming to distinguish certain types of top level
coding. On the engine level itself there is the stack, its size and
respectively certain amount of RET values it may store in LIFO schema.
Respectively the engine itself doesn't care what RETs are these:
function F0001 calling F0002,... calling F1000 - or the same function
F calling itself 1000 times. It is all the same by the allocation
demands. So in order do not switch onto Assembly language yet being
technically correct let's say that each engine has some limit of
nested calls where the chain goes from the initial Global RET point
and up to the currently executed function. This limit is the same for
the regular nested calls and for recursions as well because again on
the lower level it is all the same. So coming back to OP's question
his real question was: "How many nested control flow transfers are
allowed in the most prominent ECMAScript implementations?"
The answer is that they are still rather generous for the regular
coding. Even Safari with its lesser than 500 RET positions doesn't put
some real life limits on coding. When did anyone really needed 500 or
more different functions making nested call chain at once? I mean,
com'on now, guys...
At the same time these limits may hit noticeably recursion based code,
especially one based on infinite loops where the loop's break
determined by some condition check and not by a fixed amount of
iterations.
The other thing is that, as I said, the engine doesn't have a "stack
for regulars", a "stack for recursions" etc. It is all the same
program stack and it nearly never completely empty at runtime, so your
recursion depth tests - if done from the language itself - are going
to the top of whatever is already stored in the stack. This is why
such tests will always differ a bit circa +/-10 depending on the
structure of your test and on additional scripts already running by
the engine. So in order to get _true_ stack size one should to read
the engine specs or to query stack from outside from a C program.
I played a bit with the original test I posted so now you can run it
on any browser without manually changing every time the work-on-denial
value.
It also reminded me that JScript 5.6 had a severe stack vulnerability
bug in the original IE6 back in 2001 that allowed to do whatever you
want with the visitor's computer using specially crafted stack
overflow script. The Microsoft was in such secret panic that time that
they suggested to their corporate customers to "upgrade" from MSDN
from JScript 5.6 to JScript 5.1
I see that the current JScript 5.6 for IE6 has a quick-n-dirty
vulnerability fix for that - so it just shuts down the window being
under attack. An often question in this group is how to close the
original browser window. Here is the Astalavista way for IE6 :-)
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html lang="en_US">
<head>
<meta http-equiv="Content-type"
content="text/html; charset=iso-8859-1">
<title>Stack depth measuring</title>
<script type="text/javascript">
var fun = new Array(4000);
function test() {
for (var i=0; i<fun.length; i++) {
fun[i] = new Function('i', ''.concat(
'i++; try {fun[i](i);}',
'catch(e) {window.alert(',
'e.message.concat("\\n","max allowed: ",i));}'
)
);
}
fun[fun.length-1] = new Function('window.alert(\'OK\');');
eval(fun[0](0));
Thomas 'PointedEars' Lahn
> On May 18, 2:16 am, Thomas 'PointedEars' Lahn <PointedE...@web.de>
> wrote:
>> A recursive algorithm does not *close back* *on* itself, it *calls forward*
>> *to* itself. Hence the requirement of a stack for recursion, but not for
>> iteration.
>
> OK, let's us set the grounds first: iterations, recursions, finite
> loops, infinite loops etc. these are all top level mental constructs
> used in the programming to distinguish certain types of top level
> coding. On the engine level itself there is the stack, its size and
> respectively certain amount of RET values it may store in LIFO schema.
> Respectively the engine itself doesn't care what RETs are these:
> function F0001 calling F0002,... calling F1000 - or the same function
> F calling itself 1000 times. It is all the same by the allocation
> demands.
No, it is not. With recursion it is a different execution context than
iteration, and therefore the allocation demands must be quite different.
Besides, arguing with assembler when we know that we are dealing with a
Virtual Machine, and using eval() for testing recursion, shows again what
little your long-winded "explanations", flawed "tests", and bloated
"examples" are worth.
VK
wrote:
> No, it is not. With recursion it is a different execution context than
> iteration, and therefore the allocation demands must be quite different.
>
> Besides, arguing with assembler when we know that we are dealing with a
> Virtual Machine, and using eval() for testing recursion, shows again what
> little your long-winded "explanations", flawed "tests", and bloated
> "examples" are worth.
Do you want to learn and to find the real nature of things or just
being nasty on everyone? For the latter just start a new thread then
like "Why does the world suck" or similar so do not be OT. For the
first remove eval() wrapper and call the function directly:
//eval(fun[0](0));
fun[0](0);
That takes one extra RET position in the stack for the function test()
from where the initial call is made, so you are getting 998 instead of
999.
Peter Michaux
> Jeff Bigham <jeffrey.big...@gmail.com> writes:
> > 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.
I would say there are languages where recursion is more viable than
JavaScript. Any language that guarantees proper tail call elimination
would make it possible to program with tail call recursion and no
worries about call stack depth. Scheme is one language that makes this
guarantee.
Unfortunately one of the long standing ECMAScript 4 features was going
to be proper tail calls but apparently that made type checking too
difficult. They decided that type checking was more important. [waits
for gasp to end] I know. I was very disappointed also. I don't give a
hoot about type checking but I do care about functional programming a
lot. Oh well. That about sums up my feelings on ES4.
Peter
Jorge
> So, it appears that Javascript has a recursion limit of about 1000
> levels on FF, maybe less/more on other browsers.
javascript:(function f(p){document.write(p+'<br>'); f(p+1); })(0)
WebKit/Safari r33029 --> 139808
FF3.0pre --> 2999
IE8.0.6001 --> 2340
--Jorge
Thomas 'PointedEars' Lahn
I presume you mean Fx 3 RC 1 because I get that number there.
> IE8.0.6001 --> 2340
IE 7.0.5730.11 --> 2507
PointedEars
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee
Evertjan.
> IE 7.0.5730.11 --> 2507
Mine (IE 7.0.5730.11 under XP) does 2553
====================
function f(p){
if (!(p%500)||p>2550)
document.write(p+'<br>');
f(p+1);
};
f(0);
====================
Why the difference?
XP - Vista??
It gives a popup warning "Out of memory".
Limited "subroutine" return stack?
Other memory use does not make any difference:
====================
function f(p){
if (!(p%500)||p>2550)
document.write(p+'<br>');
var z = 'Hello world';
f(p+1);
};
f(0);
====================
--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
VK
wrote:
> Thomas 'PointedEars' Lahn wrote on 23 mei 2008 in comp.lang.javascript:
>
> > IE 7.0.5730.11 --> 2507
>
> Mine (IE 7.0.5730.11 under XP) does 2553
>
> ====================
> function f(p){
> if (!(p%500)||p>2550)
> document.write(p+'<br>');
> f(p+1);};
>
> f(0);
document.write method is implemented as a pipe so useless for stack
studies. For the actual stack studies use the test I poster earlier
at
http://groups.google.com/group/comp.lang.javascript/msg/36aff21459efb837
Dr J R Stockton
23 May 2008 02:07:41, Thomas 'PointedEars' Lahn <Point...@web.de>
posted:
>Jorge wrote:
>> Jeff Bigham wrote:
>>> So, it appears that Javascript has a recursion limit of about 1000
>>> levels on FF, maybe less/more on other browsers.
>>
>> javascript:(function f(p){document.write(p+'<br>'); f(p+1); })(0)
>IE 7.0.5730.11 --> 2507
IE 7.0.5730.13 --> 2507 with that pasted into the address bar.
With (function f(p){document.write(p+'<br>'); f(p+1); })(0) in
<URL:http://www.merlyn.demon.co.uk/js-quick.htm> : Eval 2523, NewW 2523.
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk IE7 FF2 Op9 Sf3
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Evertjan.
> On May 23, 11:29 am, "Evertjan." <exjxw.hannivo...@interxnl.net>
> wrote:
>> Thomas 'PointedEars' Lahn wrote on 23 mei 2008 in comp.lang.javascript:
>>
>> > IE 7.0.5730.11 --> 2507
>>
>> Mine (IE 7.0.5730.11 under XP) does 2553
>>
>> ====================
>> function f(p){
>> if (!(p%500)||p>2550)
>> document.write(p+'<br>');
>> f(p+1);};
>>
>> f(0);
>
> document.write method is implemented as a pipe so useless for stack
> studies.
I don't see why. Please explain.
VK
> VK wrote on 24 mei 2008 in comp.lang.javascript:
>
>
>
> > On May 23, 11:29 am, "Evertjan." <exjxw.hannivo...@interxnl.net>
> > wrote:
> >> Thomas 'PointedEars' Lahn wrote on 23 mei 2008 in comp.lang.javascript:
>
> >> > IE 7.0.5730.11 --> 2507
>
> >> Mine (IE 7.0.5730.11 under XP) does 2553
>
> >> ====================
> >> function f(p){
> >> if (!(p%500)||p>2550)
> >> document.write(p+'<br>');
> >> f(p+1);};
>
> >> f(0);
>
> > document.write method is implemented as a pipe so useless for stack
> > studies.
>
> I don't see why. Please explain.
I was wrong - it did change.
So coming back to the original issue, the maximum universal stack size
is defined by the smallest value among the browsers in considerations.
Also the factual stack size is at least 1 position smaller than the
physical stack size because the position[0] is always taken by the RET
address of the initial entry point into current context, so at least
RET 0 (exit from the current context).
This way if we do care about Safari then the universal max of RET
points is 497 (Safari 3.x 498-1)
Without Safari in consideration universal max of RET points is 999
(Firefox 2.x 1000-1)
VK
> This way if we do care about Safari then the universal max of RET
> points is 497 (Safari 3.x 498-1)
> Without Safari in consideration universal max of RET points is 999
> (Firefox 2.x 1000-1)
Because no educated guess can be made about the call chain length at
the moment of starting the recursion, one either has to trace the
chain length by using deprecated yet functional arguments.caller
property or just cut the max value for another ten positions thus 488
or 989 depending on with Safari or without it. The latter way is very
approximate of course though I believe that any algorithm of any
descent sanity never goes above that call chain size. At least I never
saw a sane counterexample and all other counterexamples were clearly
insane.