get smallest from array - recurse or loop?

J

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.offsetLeft >= small.offsetLeft)
continue;
else small = aArr;
}
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;
}
 
M

Michael Winter

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.offsetLeft >= small.offsetLeft)
continue;
else small = aArr;


Why not

for(var i = 1, n = aArr.length; i < n; ++i) {
/* This being the most significant change: */
if(aArr.offsetLeft < small.offsetLeft) {
small = aArr;
}
}
}
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.offsetLeft) ? n : s;
}
getSmallest(arr, arr.length - 1);

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

Mike
 
J

J. J. Cale

Michael Winter said:
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.offsetLeft >= small.offsetLeft)
continue;
else small = aArr;


Why not

for(var i = 1, n = aArr.length; i < n; ++i) {
/* This being the most significant change: */
if(aArr.offsetLeft < small.offsetLeft) {
small = aArr;
}
}
}
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.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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top