get smallest from array - recurse or loop?

[J. J. Cale]

In IE6 both these functions *seem* to be working.
I don't see much recursion in this group except the
occasional setTimeout problems. Besides the obvious
stack problems that can occur if one recurses too deep
are there other reasons for this that I should know about?
This example returns the position of the leftmost element
of a specific type but it could be any array or any type
of comparison regex or whatever.
Also I'm sure these can be made better. Any help?
Jimbo
#1 loop
getSmallest(document.getElementsByTagName(tagName) );
function getSmallest(aArr) {
var small = aArr[0];
for (var i=1; i < aArr.length; i++) {
if(aArr[i].offsetLeft >= small.offsetLeft)
continue;
else small = aArr[i];
}
return small;
}

#2 recursion
var a = document.getElementsByTagName(tagName);
getSmallest( a, a.length-1);
function getSmallest(aArr, n) {
if (n < 0) return false;
if(n == aArr.length-1) smallest = n;
smallest = aArr[smallest].offsetLeft <= aArr[n].offsetLeft? smallest: n;
if(getSmallest(aArr,n-1))
return aArr[smallest].offsetLeft;
return aArr[smallest].offsetLeft;
}

[Michael Winter]

On Sun, 5 Dec 2004 11:03:01 +0200, J. J. Cale <ph****@netvision.net.il>
wrote:

In IE6 both these functions *seem* to be working.
An important thing to note is that they depend on at least one element in
the array. The behaviour the two alternatives is also very different. The
first version will return a reference to the left-most element, or
undefined if there are no elements in the array. The second version will
return smallest offset value, or false if there are no elements in the
array.

[snip]
Besides the obvious stack problems that can occur if one recurses too
deep are there other reasons for this that I should know about?
Recursion tends to be inefficient as function calls have the overhead of
setting up a new execution context. Loops are quicker.

[snip]
getSmallest(document.getElementsByTagName(tagName) );
function getSmallest(aArr) {
var small = aArr[0];
for (var i=1; i < aArr.length; i++) {
if(aArr[i].offsetLeft >= small.offsetLeft)
continue;
else small = aArr[i];
Why not

for(var i = 1, n = aArr.length; i < n; ++i) {
/* This being the most significant change: */
if(aArr[i].offsetLeft < small.offsetLeft) {
small = aArr[i];
}
}
}
return small;
}

#2 recursion
var a = document.getElementsByTagName(tagName);
getSmallest( a, a.length-1);
function getSmallest(aArr, n) {
if (n < 0) return false;
if(n == aArr.length-1) smallest = n;
smallest = aArr[smallest].offsetLeft <= aArr[n].offsetLeft?
smallest: n;
if(getSmallest(aArr,n-1))
This would also evaluate to false if the offset value returned below was
zero.
return aArr[smallest].offsetLeft;
return aArr[smallest].offsetLeft;
That's bizarre: if the result from the recursive call evaluates to true,
return the smallest offset value. Otherwise, return the same thing.
}

This is a much reduced version, but it too differs from both previous
versions. :) It will return the array index of the left-most elements, or
-1 if there are no elements in the array.

function getSmallest(arr, n) {var s;
if(n < 0) {return arr.length ? 0 : -1;}
s = getSmallest(arr, n - 1);
return (arr[n].offsetLeft < arr[s].offsetLeft) ? n : s;
}
getSmallest(arr, arr.length - 1);

Really, I'd just stick to the loop version.

Mike

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

[J. J. Cale]

"Michael Winter" <M.******@blueyonder.co.invalid> wrote in message
news:opsijcl4olx13kvk@atlantis...

On Sun, 5 Dec 2004 11:03:01 +0200, J. J. Cale <ph****@netvision.net.il>
wrote:

In IE6 both these functions *seem* to be working.
An important thing to note is that they depend on at least one element in
the array. The behaviour the two alternatives is also very different. The
first version will return a reference to the left-most element, or
undefined if there are no elements in the array. The second version will
return smallest offset value, or false if there are no elements in the
array.

Thank you for pointing that out Michael. I originally intended to
return an index to the object in both examples but pulled these
out of some operative code on the fly. I realize how important
it is to check the returns properly and handle failures correctly.
[snip]

Besides the obvious stack problems that can occur if one recurses too
deep are there other reasons for this that I should know about?
Recursion tends to be inefficient as function calls have the overhead of
setting up a new execution context. Loops are quicker.

Ahh. That's what I was looking for!
[snip]

getSmallest(document.getElementsByTagName(tagName) );
function getSmallest(aArr) {
var small = aArr[0];
for (var i=1; i < aArr.length; i++) {
if(aArr[i].offsetLeft >= small.offsetLeft)
continue;
else small = aArr[i];
Why not

for(var i = 1, n = aArr.length; i < n; ++i) {
/* This being the most significant change: */
if(aArr[i].offsetLeft < small.offsetLeft) {
small = aArr[i];
}
}

}
return small;
}

#2 recursion
var a = document.getElementsByTagName(tagName);
getSmallest( a, a.length-1);
function getSmallest(aArr, n) {
if (n < 0) return false;
if(n == aArr.length-1) smallest = n;
smallest = aArr[smallest].offsetLeft <= aArr[n].offsetLeft?
smallest: n;
if(getSmallest(aArr,n-1))

This would also evaluate to false if the offset value returned below was
zero.

return aArr[smallest].offsetLeft;
return aArr[smallest].offsetLeft;

That's bizarre: if the result from the recursive call evaluates to true,
return the smallest offset value. Otherwise, return the same thing.

I thought so too :>) that's why the *seems* you quoted. I thought it
best to serve up some code not just the simple question and I don't
write recursions every day. Good drill for an old programmer.
I wrote (hacked) this on the fly from bits that I've been working on.
Thus two differently oriented versions neither of which returns
an index as your fix does.

}

This is a much reduced version, but it too differs from both previous
versions. :) It will return the array index of the left-most elements, or
-1 if there are no elements in the array.

function getSmallest(arr, n) {var s;
if(n < 0) {return arr.length ? 0 : -1;}
s = getSmallest(arr, n - 1);
return (arr[n].offsetLeft < arr[s].offsetLeft) ? n : s;
}
getSmallest(arr, arr.length - 1);

Really, I'd just stick to the loop version.

Amen
Mike

Thanks Mike. To the point answer and thanks for the fixes.
Saves me a lot of mileage.
Have a nice day.
Jimbo -- Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.