recursive functions

[Zero Tolerance]

im aware of what a recursive function is.....but having a lil trouble coding it...

i have done some simple recursive calls like reading from a string and printing out characters from it...or whatnot

but i am a lil stumped on this problem

we are working to write a recursive function that searches via "divide and conquer" binary

so if i want to find the largest number in an array

ex.

maxArray(<1,6,8,3>)
return max(maxArray(<1,6>), maxArray(<8,3>))

trees off to:
(1)
maxArray(<1,6>)
return max(maxArray(<1>), maxArray(<6>)

(2)
maxArray(<8,3>)
return max(maxArray(<8>), maxArray(<3>))

trees off to:
(1a)
maxArray(<1>)
return 1
(1b)
maxArray(<6>)
return 6

(2a)
maxArray(<8>)
return 8
(2b)
maxArray(<3>)
return 3

I copied that box diagram from the book....and it makes sense to me

what im not sure about is only using one recursive function to compare the binary search results when the maxArray is split

i know that the two sides of the block diagram needs to be compared each time to see which side has the larger number at that comparison.....and switch back and forth saving the largest number to be compared on the next result

i just cant think of a way to do this in one recursive function

can anyone give an example of a recursive function that does this or one that at least will give results of a binary search?

thanks!

[Bond]

Is there always an even number of array elements?

[Zero Tolerance]

in this situation there is

[Greg]

This is anaconda's forte'. Hopefully he'll have a minute to look at it.

[Zero Tolerance]

just for the record....the (1) (2) (1a) (1b) (2a) (2b) have nothing to do with the box trace above

i just labled it so you could tell how the box trace would be written out

didnt wanna confuse anyone

[Anaconda]

sorry i was away for thge weekend.. give me a bit, and I'll try to post something more complete.

But for starters. The MaxArray function works by (at the head end) breaking (decomposing) ther array down to it's component parts (array elements) and then on the tail end comparing the results, and only returning the higher of the two values. In essence this works like a sieve.

[Zero Tolerance]

yes snake...thats how i understand it to work...just not sure how to go about coding it

i took a couple minutes and drew the blocktrace out just so there is not any confusion on my typed out trace above

[Zero Tolerance]

i want to correct myself....my initial post stated that i wanted to find the largest NUMBER of an array

thats a typo on my behalf.....i should of said ELEMENT instead of number

i simply was just taking the value of the element in my thought process as the number...which it literally is....but the correct wording of it would be element rather than number

sorry!

[Anaconda]

The following code is quite simple, it uses recursion to continuously sub-divide the array (or sub-array) in half until it has reached a single element, at that point it returns that single element. The previous recursion level will then compare the results of the 2 halves and return only the greater of the 2 values. Each level will then compare the results, returning the greater, until we have returned to the original caller, the result will then be the largest number in the array. Memory wise this impolementation is very efficient since it does not make a new copy of the array (or sub-array) for each recursive call, instead we pass an index and limit, to define the part of the array the function should be looking at.

If you wanted to hide some of the extra parameters, you could wrap MaxArray() with another function that only takes the array (and possibly it's length) as parameters. Note that if you do not take length as a parameter, you will need a method for determining the arrays size.

The search is initiated by calling he function, with the array, a start index of zero and the length of the array.

Also you may want to consider returning the index to the element, and not the value if the element. Returning the index can provide you with additional useful information, depending on what you are going to do with the data next.


int MaxArray(int myArray[], int arrayStart, int arraySize) {
int r1,r2,n;

// first divide the array down, until we have reached a single element

// recursion stop condition
if(arraySize==1) // return the single element
return myArray[arrayStart];

// recursive.. call ourself with 1/2 the array
n=arraySize/2; // find the midpoint of size

r1 = MaxArray(myArray, ArrayStart, n); // left branch

// we use Size-N here in case we have an odd number size
// the additonal element will be handled by the 'right' branch
r2 = MaxArray(myArray, ArrayStart+n, ArraySize-n); // right branch

// return the greater result
return (r1>r2)?r1:r2;
}


Note: by using the Size-N in the second recursive call, we guarantee that all elements will be traversed, otherwise the last element in an odd length array will be dropped. This case would also, eventually, occur if the array was not of a size that was a power of two.

example of the flow of the above:

array=[21,22,23,24,25,26]

MaxArray(array, 0, 6) [21,22,23,24,25,26]

-MaxArray(array,0,3) [21,22,23] ** sub divide, and traverse left side
--MaxArray(array,0,1) [21] ** subdivide, traverse left -- odd number here, integer round down
---return 21 ** single element return element
--MaxArray(array,1,2) [22,23] ** subdivide, traverse right -- pick up the extra element here (integer round up)
---MaxArray(array,1,1) [22] ** subdivide traverse left
----return 22 ** single element, return
---MaxArray(array,2,1) [23] ** subdivide traverse right
----return 23 ** single element return
---compare 22>23 ==> return 23 ** compare left to right, return greter
--compare 21>23 ==> return 23 ** compare left to right, return greater
-MaxArray(array,3,3) [24,25,26] ** sub divide, and traverse right side
--MaxArray(array,3,1) [24]
---return 24
--MaxArray(array,4,2) [25,26]
---MaxArray(array,4,1) [25]
----return 25
---MaxArray(array,5,1) [26]
----return 26
---compare 25>26 ==> return 26
--compare 24 > 26 ==> return 26
-compare 23>26 ==> return 26



The above is just one way to solve the problem.. there are many others, most of which will be more efficient as well.

Just a small not on recursion. C is not a recursive friendly language, as such you should never run recursive functions on extremely large data sets, or you will eventually overflow the stack, as each call sets up a new stack frame for the function.

[Anaconda]

I should clarify one line of code, in case you are not familiar with the inline conditional statement.

the line

return (r1>r2)?r1:r2;

is the same as the following

if(r1>r2)
return r1;
else
return r2;


of course if you were a real hacker and wanted to be clever, you might write the whole thing as follows

int MaxArray(int a[], int s) {
int n;
return (s==1)?*a:((s=MaxArray(&a[n=s>>1],s-n))>(n=MaxArray(a,n)))?s:n;
}


Then again, a real hacker would never implement a simple max search like this, as it's inefficient :p A simple linear search, would execute several times faster in this case. and would carry a much smaller memory footprint.

[Zero Tolerance]

shouldnt your last line in your code "flow" be 23 instead of 21?

if thats not a typo...why would the last compare be between 21 > 26??

and thanks for the great post!....explains it in depth and at least easier for me to understand than the textbook

[Anaconda]

sorry, you are correct.. typo on my part.. actually it was more like a brain fart I've gone and corrected it.

[Bond]

Shouldn't your MaxArrayWorker calls really be MaxArray calls?

[Anaconda]

:eek: oops! lol.. that was from an earlier draft, before I simplified it.. I originally had MaxArray as a wrapper around the 'worker' version which was the recursive part, to hide some of the additional parameters requred for recursion. Since it's usually good practice to hide these implementation details, and it tends prevents further error. Though sometimes confuses things a bit, so i removed it.

This always happens when I try to make a piece of code easy to understand.. I end up writing it 3 or 4 times, and inevetably leave some snippit of a previous version in there. Thanks for catching that.. I've fixed it to prevent further confusion.

[Zero Tolerance]

again...thanks!

[Anaconda]

no problem.. glad I could help

[Zero Tolerance]

glad Bond caught that 'worker' deal

im still too much of a noob to know that it wasnt spose to be there!

LOL

[Bond]

Well, it's easy to sit back and find errors in OTHER people's code! =)