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

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>

On May 17, 8:49 pm, Thomas 'PointedEars' Lahn <PointedE... (AT) web (DOT) 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?

VK wrote:

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

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$8300dec7 (AT) news (DOT) demon.co.uk>

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

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.

VK wrote:

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


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>

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

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.

VK wrote:

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

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

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.

/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.'