View Full Version : Recursion getting incrementally slower?

02-13-2004, 03:14 AM
Before unloading with a bunch of potentially unnecessary details...

I'll just ask:
What would make a recursive function execute slower & slower, the longer it ran? :confused:

Ok, maybe one detail: :D
The test involved iterating & outputting thousands of values to a textarea...

02-13-2004, 07:41 AM
Using innerHTML to dynamically change values for each pass of the recursion would, for instance.

Any code sample?

02-13-2004, 10:51 AM
Here's a generic example.

Removing the highlighted line will show the difference between accumulating output, and just running the number.


<script type="text/JavaScript">

var i, interval, stop;

function Recurse(startTime, n, oForm){
var et, ETA, H, M, m, S, s;

et = new Date().getTime() - startTime;

if(et % 100 == 0){
ETA = new Date(((n - i) / (i / et)));
H = ETA.getUTCHours();
M = ETA.getMinutes();
S = ETA.getSeconds();
M < 10 ? m = "0" + M : m = M;
S < 10 ? s = "0" + S : s = S;
oForm.timeRem.value = H + ":" + m + ":" + s;

oForm.progress.value = i;
oForm.percentage.value = Math.floor(((i / n) * 100)) + "%";

oForm.txt.value += "Output Value # " + i + "\n";

if (i >= n || stop){controlUpdate("Complete");}

function controlUpdate(callString){
var oForm, n, startTime;
oForm = document.testForm;


case "Start" :
n = new Number(oForm.test.value);
if(isNaN(n) || n < 1){
alert("loop value must be a number greater than 0. ");
i = 0;
stop = false;
oForm.cancel.disabled = 0;
oForm.start.disabled = 1;
oForm.test.disabled = 1;
startTime = new Date().getTime();
interval = setInterval(function(){Recurse(startTime, n, oForm);},1);

case "Cancel" :
stop = true;
oForm.rs.disabled = 0;
oForm.cancel.disabled = 1;

case "Complete" :
oForm.rs.disabled = 0;

case "Reset" :
oForm.cancel.disabled = 1;
oForm.start.disabled = 0;
oForm.test.disabled = 0;
oForm.rs.disabled = 1;

<style type="text/css">


<form name="testForm" onreset="controlUpdate('Reset')">
<label>i :</label><input name="progress" size="10" readonly>
<label>% :</label><input name="percentage" size="10" readonly>
<label>ETA :</label><input name="timeRem" size="10" readonly>
<label>n :</label><input name="test" size="10" value="9999" maxlength="5">
<input name="start" type="button" value="Start" onclick="controlUpdate('Start')">
<input name="cancel" type="button" value="Cancel" disabled onclick="controlUpdate('Cancel')">
<input name="rs" type="reset" disabled>
<textarea name="txt" cols="40" rows="20"></textarea>


Of course, I'd probably never end up with such a high number in a collection, but a more involved output would take me a while to demonstrate (without using the Shell Object). The point at which the execution slows is somewhat consistent, though.

Roy Sinclair
02-13-2004, 03:51 PM
Each time you += more content onto the string enough free memory has to be found to hold the new longer string and then the shorter string is released to free memory. When the string is short that overhead may not be very noticable but the longer the string gets the more likely that no free memory that the browser already has will be able to hold it so the browser has to go to the OS for more memory. Once it's done that a few times it'll have several chunks of free memory that it'll try to consolodate so there's also overhead in that process.

If your system is short on physical memory you could also get into a situation where you're swapping the string out to disk and back in which increases the overhead by several magnitudes.

02-13-2004, 06:19 PM
Well, there is another factor. setInterval for the first doesn't execute until the latest run has finished, so it will be stacking runs that were not finished until the first one returns. Second, you use a WAY too low interval. Win9x has an operative system time window of 55 ms, WinNT has a window of 10 ms. Trying to use lower times than those windows WILL lead to stacking and thus reduced speed. I don't know whether MacOS 9, MacOS X and *nix have the same methodology of using operative system wide time windows, but it wouldn't surprise me.

02-14-2004, 02:25 AM
Thank you both for the info. :)

I can see the difference in memory usage, now -- after trying some DOM methods; and it looks like setTimeout is more useful here, given that it wouldn't allow for stacking to occur (if that's right).

So, I'm just left wondering if the delay in milliseconds for setTimeout should also be set, at minimum, to the "system time window" -- or does that only apply to setInterval?

02-14-2004, 02:55 AM
That applies to both setTimeout and setInterval. It's what you could call a definite lower limit for how often you can call things in an operative system provided environment. The reason for this window is that you don't want these kinds of processes to be allowed to take so much time that actually just polling the times hogs the CPU. You see, what the computer does when timing, is that it continually asks the processor for the system time, then replies to the program, so to know that 10 ms has passed, you esentially have to ask for the time continuously until the set time is reach, at which point you stop polling the system time and start your process. If you use setInterval, a new polling will commence directly after the previous one has stopped. The operative system time windows limits the rate of polling to preserve system responsitivity and reduce system load.

02-14-2004, 03:09 AM
Ah, that's understandable -- which makes it seem odd that a higher minimum delay was not built into the methods.

Thanks again.