need help with recursion's base case...

i seem to have a huge problem with finding a proper base case for my recursive program.... can anyone help.... i just can't get it...


here's some code....




// Task: Implement (MaxArray), discussed in the section "Finding the
// Largest Item in an Array," as a C++ function. What other
// recursive definitions of (MaxArray) can you describe?
//
// Preconditions: Every recursive call must make the original program
// smaller by at least a half. There must be a base case,
// which in fact has to be reached by one of the recursive
// calls to the function.
//
// Postconditions: At the end the result has to come out victorious and
// the program will point to the largest number.
//
////////////////////////////////////////////////////////////////////////////

//---------------------------------------------------------------------------
// Preprocessor directives...

#include <iostream>
#include <cstdlib>
using namespace std;

//---------------------------------------------------------------------------
// Global constant variables...

const int MaxIntegers = 10;
// int Highest;

//---------------------------------------------------------------------------
// Functions declarations...

int MaxArray(int Array[], int First, int Last);
int Compare(int Largest);

//---------------------------------------------------------------------------

int main()
{
cout << "This program will ask you to input 10 integers. \n"
<< "After you have done so, the computer will display all \n"
<< "of these integers and display the one that is the largest \n"
<< "out of these 10 integers. \n\n\n";

int Array[MaxIntegers];

for (int i = 0; i < MaxIntegers; i++)
{
cout << "Please enter integer # " << i + 1 << endl;
cin >> Array[i];
cout << endl; // flushes the buffer
}

cout << "These are the integers the you have entered: \n\n";

for (int j = 0; j < MaxIntegers; j++)
{
cout << Array[j] << ", ";
}

cout << "\n\n" << endl; // flushes the buffer

int First = 0;
int Last = (MaxIntegers - 1);

int Highest = MaxArray(Array, First, Last); // function call...

cout << "The largest integer is " << Highest << endl;

system("pause");

return 0;
}
//---------------------------------------------------------------------------
// Function definition (implementation)...

int MaxArray(int Array[], int First, int Last)
{
int Largest;
int Biggest;
int Mid = (Last + First) / 2; // finding midpoint

if (Last = Last)
{
Largest = Array[Last]; // not necessarily true...check it.!!!
Biggest = Compare(Largest); // have to send it here...somewhere...
} // need to have a different base case

else
{
MaxArray(Array, First, Mid); // recursive call...
MaxArray(Array, (Mid + 1), Last);
}
// i have to send the results somewhere to somehow compare
// then in term of size...... hmmm... ? and return the biggest one.

return Biggest;
}
//---------------------------------------------------------------------------
// Function definition (implementation)...

int Compare(int Largest)
{
int Biggest;

if (Largest > Biggest)
{
Biggest = Largest;
}

return Biggest;
}
//---------------------------------------------------------------------------



i think the problem is in the function MaxArray

in the "if" statement ... if(Last == First)

seems to be a wrong base case or maybe something else is wrong


can anyone give me a hand....????

thanx
matheo917

Code:

---

// max number in the array is returned..
int MaxArray(int array[], int first, int last)
{
  if ( first == last )
      return array[last];
  else
  {
      int max = MaxArray ( array, first-1, last );
      return (max > array[first]) ? max : array[first] ;
  }
}

---

I think this will work.. i did it in a hurry.. so if there are errors, debug for urself. but i think u'll get the general idea

i've tried this code but unfortunatelly it doesn't work... seams like it's due to the same problem --> the base case....if(first == last)

hmmm.....

still trying

like i said i did this in a hurry... from what i see, obviously you didn't bother to even debug the thing. the only thing that's wrong with the code is that i use - 1 in this:

Code:

---

      int max = MaxArray ( array, first-1, last );

---

of course if you think about it -1 doesn't make a lotta sense. because if you start out with first as 0 you'll get negative one as your array index..

so if you change that to this:

Code:

---

      int max = MaxArray ( array, first+1, last );

---

then the code will work..
oh, please beware not to put the size of the array into the "last" variable because you are using index not size for this function. that's all. have fun coding! :cool:

Umm, why do this with array indices? Try this, it will probably work much easier:

Code:

---


int maxArray(int * a, int size){
  if (size == 1)
    return a[0];
  int left, right;
  int * mid = a + size/2; // mid = first element in right 1/2
  left = maxArray(a,mid - a);
  right = maxArray(mid,size-(mid - a));
  return max(left,right);
}

---

Now, you can still pass an array as always, because passing an array is defined as passing a pointer to the first element.

I just tested this both with an array declared as an array, and one declared by a malloc() of an int *. It works just fine, and it's certainly simpler.

Hm.. I think the performance of our algorithms are pretty similar. because ur codes are breaking the array in two, a binary tree will represent it pretty well. and since you are traversing the whole tree. so you'll get O(n). and that's the same as my algorithm. my codes are only a reverse of the iterate version of this function (i run the whole thing to the end and compare that from the bottom up). but i must say, both aren't as effiecient as the original iterated version. also i need to point out that passing indices into this function does have one advantage. with array indices, you can find the max of any portion in your array (e.g. from index 5 to 50). this, in a way, is much more flexible.. hm.. like most of the time, my analysis of these algorithms could be wrong. please feel free to correct me if you may. :cool:

You can pass parts of an array.

You want to start at element 5 and go till element 50? This is 46 elements (50 - 5 + 1). You're skipping the first 5 elements (0 through 4).

maxArray(array+5,46);

Yours is actually slower -- it is really, in essence, a linear search. The goal was to break the array in (mostly equal) halves, and search each half with recursion. You break it into 2 arrays, but one will be single-element, the other will be size-1 elements.

In actual number of comparisons, each method is equal to linear search. Now, if the array is *sorted*, a slight modification of my method would be much faster. In this case, each level you moved down the tree would halve the data you had to search.

The only real flaw with your solution is the preconditions on the task: Make the array smaller by at least half.

You are right your method is better.. and takes less memory. But since the guy started out with indexing header, I just follow whatever he has. and i must ask, what's the point of putting a sorted array into a max function? u know the max number is either the first or the last element in the array (depending on ur sorting algorithm..) unless the way u sort the array is some speically coded method.. i guess my point is in general max function is O(n). and like i said the most effiecient method is still the original iterated version (no overhead variables, it's one time kinda deal)..

Yeah, a max function wouldn't need searching to find the val in a sorted array... I guess I was thinking of generalizing this to a binary search method.