OSDev.org

I have a school project which must have a recursive function to find the mode of a set of data. Personally, I think it's a waste of time and effort; iteration is much easier and faster in this case. My original idea was to create a list of distinct elements in the set, and a list of the number of times each element appears in the set. This can be easily set up using a recursive method. Then iteratively look through them and return the most frequent element, or null (I'm working in Java) if there's no mode. My question is, does anyone know of a better implementation than this, still using a recursive method? I don't need source code...just an idea. ^_~

perhaps what we seek is the simplest available recursive algorithm that can get the job done, regardless of performance concerns
in recursion you let it solve itself


java.lang.object.hashcode() ?

to come to think of, a set's primary attribute is lack of order
to assume it can be represented as a sequential one-way list is not wise
for example, a network crawler can be easily lost in the graph of nodes
recursion unconciously keeps track of its actions
one thing recursion cant do is return immediately
a method like getNextNode() must be implemented differently

Well, I can guarrantee the data will be some random array of Integers, which is why I didn't come up with something so obtuse. ^^

I am assuming that if they want a recursive algorithm, then, that simply rewriting the iterative version using TR won't do, eh? So much for cheap ways out...

From the description of the project, the professor probably has in mind some relatively simple, but non-intuitive, method that can be found with some thought. Hmmmn, now what are the properties of the mode of an array again (quick lookup). Ah, right. Most common number appearing in a list.

OK, so the obvious iterative version is:

[tt]f(a) <-
k <- length of a
c[sub]global[/sub] <- 0
n <- a[sub]0[/sub]

for each i from 0 to k
c[sub]local[/sub] <- 0
for each j from 0 to k
if i = j
continue
else if a[sub]i[/sub] = a[sub]j[/sub]
increment c[sub]local[/sub]

if c[sub]local[/sub] > c[sub]global[/sub]
n <- a[sub]i[/sub]
c[sub]global[/sub] <- c[sub]local[/sub]
return n[/tt]

Now, if you think about it, that's not a very efficient algorithm; at it requires k[sup]2[/sup] passes over the array. It is, in other words, an O(n[sup]2[/sup]) algorithm in time. There is also no obvious recursive equivalent, except by simply replacing the loop with a tail call; since that is effectively a form of iteration, this is of little use to you.

A better approach might be if you could sort the array first; then you could reduce it to a single pass:

[tt]
f(a) <-
k <- length of a
n, m <- a[sub]0[/sub]
c[sub]global[/sub] <- 1
c[sub]local[/sub] <- 1

for each i from 1 to k
if a[sub]i[/sub] = m
increment c[sub]local[/sub]
else
if c[sub]local[/sub] > c[sub]global[/sub]
n <- m
c[sub]global[/sub] <- c[sub]local[/sub]
m <- a[sub]i[/sub]
c[sub]local[/sub] <- 1
return n[/tt]

This should be better; it ought to give O(n) (i.e., linear) performance in time. It also lends itself to an obvious recursive form:

[tt]f(a, s) <-
k <- (length of a) - s
n <- a[sub]s[/sub]
c <- 1

c <- c + g(n, a, s + 1)

T <- f(a, s + c)
if T{c} < c
T <- {c, n}
return T[/tt]

where

[tt]g(n, a, s) <-
c <- 0

if a[sub]s[/sub] = n
c <- 1 + g(n, a, s + 1)
return c[/tt]

The problem with this is that the return value is a complex data type holding both the count and the number (represented here as a tuple; in Java it would be an object class of some sort). This is the best I have thought of right now; honestly, I doubt it gains you anything over what you are using now.

Keep in mind that this hasn't been tested yet, so I may have made an error in the algorithms especially that last one. I'll see if I can try impementing myself in Scheme really quickly; while that won't help you directly, it would at least show whether it is valid.

Here's the Scheme version I mentioned. It's hard to say how well it would translate into Java, however. Especially if you don't know Scheme.

I don't know Scheme at all. However, it resembles a melding between SCI Studio's language and Forth, so I'm having almost no trouble picking apart the basic jist of the code. Thanks for your cool ideas, though. ^^

Thanks. If it helps any, you could take a look at my Scheme tutorial thread if you get stuck; with such a small program, it shouldn't be necessary, though.

Actually, your comments about sorting the list got me thinking about the quick-sort algorithm, which I think would fit this application very nicely. Afterall, the final "leaf list" in the quick-sort algorithm is a set of identical elements, so just recording the element and it's count would work nicely for finding the mode. I apologize if my terminology is bass-ackwards, but I'm totally self taught, so I tend to make up names as I go. ^_~

That sounds like a good approach, definitely.