469,303 Members | 1,796 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,303 developers. It's quick & easy.

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

Jun 27 '08 #1
30 7567
Jeff Bigham <je************@gmail.comwrites:
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 - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Jun 27 '08 #2
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....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.
Jun 27 '08 #3
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
Jun 27 '08 #4
VK
On May 17, 6:28 pm, Thomas 'PointedEars' Lahn <PointedE...@web.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
Jun 27 '08 #5
Thomas 'PointedEars' Lahn <Po*********@web.dewrites:
I don't think so. Every recursion can be rewritten into an iteration, no?
It can, just as any iteration can be rewritten into recursion.
For some problems, the recursive specification is much more direct and
straightforward.

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

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Jun 27 '08 #6
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
Jun 27 '08 #7
VK
On May 17, 7:37 pm, Lasse Reichstein Nielsen <l...@hotpop.comwrote:
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.
Jun 27 '08 #8
Thomas 'PointedEars' Lahn <Po*********@web.dewrites:
VK wrote:
>[...] Thomas 'PointedEars' Lahn [...] wrote:
>>You don't even know what you are
talking about to begin with: There is no "Javascript". There are
JavaScript, JScript, and other ECMAScript implementations.

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

That is not an opinion, it is a fact accepted by people who know what
they are talking about (not you, of course).
Facts does not define how language works. People do.
I am fully aware of the number of different implementation of languages
that are (more or less) ECMAScript compliant, and runtime environments
that are (more or less) W3C DOM compliant.

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

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

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

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

If anybody want this use of the word "javascript" to go away, they
need to come up with a better name. Anything else is flailing at
windmills.
There have been a number of 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 - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Jun 27 '08 #9
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
Jun 27 '08 #10
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
Jun 27 '08 #11
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>
Jun 27 '08 #12
VK
On May 17, 8:49 pm, Thomas 'PointedEars' Lahn <PointedE...@web.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?
Jun 27 '08 #13
VK wrote:
On May 17, 8:49 pm, Thomas 'PointedEars' Lahn <PointedE...@web.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>
Jun 27 '08 #14
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, <f8*******************@news.demon.co.uk>
Jun 27 '08 #15
VK
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.
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.
Jun 27 '08 #16
VK wrote:
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
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>
Jun 27 '08 #17
VK
>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.
Jun 27 '08 #18
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
Jun 27 '08 #19
Thomas 'PointedEars' Lahn <Po*********@web.dewrites:
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 - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Jun 27 '08 #20
VK wrote:
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.
PointedEars
--
var bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16
Jun 27 '08 #21
VK
On May 18, 2:25 pm, Thomas 'PointedEars' Lahn <PointedE...@web.de>
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.
Jun 27 '08 #22
On May 17, 4:27 am, Lasse Reichstein Nielsen <l...@hotpop.comwrote:
Jeff Bigham <jeffrey.big...@gmail.comwrites:
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
Jun 27 '08 #23
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)

WebKit/Safari r33029 --139808
FF3.0pre --2999
IE8.0.6001 --2340

--Jorge
Jun 27 '08 #24
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)

WebKit/Safari r33029 --139808
FF3.0pre --2999
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
Jun 27 '08 #25
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);
====================

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)
Jun 27 '08 #26
VK
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. For the actual stack studies use the test I poster earlier
at
http://groups.google.com/group/comp....aff21459efb837
Jun 27 '08 #27
In comp.lang.javascript message <48**************@PointedEars.de>, Fri,
23 May 2008 02:07:41, Thomas 'PointedEars' Lahn <Po*********@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.htmjscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/TP/BP/Delphi/jscr/&c, FAQ items, links.
Jun 27 '08 #28
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.

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
Jun 27 '08 #29
VK
On May 24, 7:13 pm, "Evertjan." <exjxw.hannivo...@interxnl.netwrote:
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)
Jun 27 '08 #30
VK
On May 25, 12:29 am, VK <schools_r...@yahoo.comwrote:
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.
Jun 27 '08 #31

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Georgy Pruss | last post: by
19 posts views Thread by Kay Schluehr | last post: by
13 posts views Thread by robert | last post: by
6 posts views Thread by Andre Kempe | last post: by
10 posts views Thread by elventear | last post: by
14 posts views Thread by asit | last post: by
2 posts views Thread by Victor Lin | last post: by
6 posts views Thread by globalrev | last post: by
reply views Thread by zhoujie | last post: by
reply views Thread by harlem98 | last post: by
1 post views Thread by Geralt96 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.