asked on

Output the last run of a recursive function???

I made a recursive function called MinimumObject, which searches a vector of objects for the alphabetically lowest value.
It works by splitting the vector in two until there are only 1 or 2 elements then compares them.

If I "cout" the values in my FindMin function as I have done below, I am given a list of the smaller of 2 strings and the last one is my minimum. But how do I output just the last value and not the full list?

I have int mode because I was trying to have the comments show up only in mode = 1 and have mode 2 show just the answer. But after hours and hours of trying different combinations of if(mode == 1 or 2) statements I still can't figure out how to go about outputting the last value by its self.

please someone help me

string MinimumObject(vector<Associate> &Members, string key, int mode)
{
      vector<Associate> Members2;

      if (Members.size() == 0)
            return "NULL";

      if (Members.size() == 1)
            {
            return Members[0].getKey(key);
            }

      if (Members.size() == 2)
            {
            return FindMin(Members[0].getKey(key), Members[1].getKey(key));
            }
      else
            {
             Members2 = split(Members); // Split Members vector in 2
            return FindMin(MinimumObject(Members, key, mode), MinimumObject(Members2, key, mode));
            }
}

//********************************************************

//INPUT: Two strings
//OUTPUT: Returns the alphabeticly lowest value of the 2 strings.
string FindMin(string a, string b)
{
            bool first = (a<=b);
            if (first)
            {
                  cout<<a<<"\n";
                  return a;
            }
            else
            {
                  cout<<b<<"\n";
                  return b;
            }
}

AlexFM

FindMin has now idea whether it is called last time or not. By the way, this is good design - it shouldn't know this. However, if you want to output only last result from FindMin, add parameter to it:

string FindMin(string a, string b, bool bLastCall)
{
bool first = (a<=b);
if (first)
{
if ( bLastCall )
cout<<a<<"\n";
return a;
}
else
{
if ( bLastCall )
cout<<b<<"\n";
return b;
}
}

Caller:

if (Members.size() == 2)
{
return FindMin(Members[0].getKey(key), Members[1].getKey(key), true);
}
else
{
Members2 = split(Members); // Split Members vector in 2
return FindMin(MinimumObject(Members, key, mode), MinimumObject(Members2, key, mode), false);
}

(I am not sure that change in caller code is right, but general idea is only caller knows that FinfMin runs last time).

RiMZ

ASKER

Doing that made the list shorter but not just one. Also the last one wasn't the minimum anymore.

Sys_Prog

Hi RiMZ

If u r returning the minimum string, then why don't u use the return value of your MinimumObject() function itself for printing the minimum value

i.e. Use a cout at the place [say in main()] from where u r calling this MinimumObject() function

RiMZ

ASKER

Thanks Sys,

That works but unfortunatly it shows me that my function is not returning the smallest value in the vector. Anyone know what is wrong with my recursive call?

string MinimumObject(vector<Associate> &Members, string key, int mode)
{
      vector<Associate> Members2;

      if (Members.size() == 0)
            return "NULL";

      if (Members.size() == 1)
            {
            return Members[0].getKey(key);
            }

      if (Members.size() == 2)
            {
            return FindMin(Members[0].getKey(key), Members[1].getKey(key));
            }

      else
            {
             Members2 = split(Members); // Split Members vector
            return FindMin(MinimumObject(Members, key, mode), MinimumObject(Members2, key, mode));
            }
}

//INPUT: Two strings
//OUTPUT: Returns the alphabeticly lowest value of the 2 strings.
string FindMin(string a, string b)
{
            bool first = (a<=b);
            if (first)
            {
                  return a;
            }
            else
            {
                  return b;
            }
}

//***************************************

It should work something like this.... Say you have 8 elements

12345678 // not 2 or 1 divide vector
1234 5678 // not 2 or 1 divide vector 1234 and 5678
12 34 56 78 // min of 1&2 , min of 3&4, min of 5&6, min of 7&8
1 3 5 7 .....
1 5
1

Sys_Prog

Check if your list is getting splitted properly

RiMZ

ASKER

Yes it does it splits it like this but with strings instead of numbers

Members = 1234
Members2 = 8765

or in case of odd number of elements

Members = 12345
Members2 = 9876

Member_2_1001466

I would place a cout in FindMin:
string FindMin(string a, string b)
{
cout << a << "\t" << b << "\t";
bool first = (a<=b);
if (first)
{
cout << "min is a" << endl;
return a;
}
else
{
cout << "min is b" << endl;
return b;
}
}

In that way you can check at which stage the code does not work as expected.

Sys_Prog

I think he want's the min string to be printed and this is not just for debugging purpose, Thus it would be better to place it as I had posted in my previous post

Sys_Prog

Ok, split is working, so the culprit can be the findmin() part. Check that and if that works, then we would see the actual culprit - the recursive function

RiMZ

ASKER

FindMin works fine. I output the 2 strings and the smaller is always returned.

Any ideas on how to change the recursive function?

Member_2_1001466

I perhaps found a solution:

Add another parameter to MinObject: int level. This should be 0 when called from main () and be increased in every recursion:
if (Members.size() == 2)
{
return FindMin(Members[0].getKey(key), Members[1].getKey(key), level+1);
}

else
{
Members2 = split(Members); // Split Members vector
return FindMin(MinimumObject(Members, key, mode, level+1), MinimumObject(Members2, key, mode, level+1));
}
}

And now you add to the Members.size == 1 and == 2 cases an if like

[snip]
if (Members.size() == 1)
{
string retStr = Members[0].getKey(key);
if (level == 0)
cout << retStr << endl;
}
return retStr;

if (Members.size() == 2)
{
string retStr = FindMin(Members[0].getKey(key), Members[1].getKey(key));
if (level == 0)
cout << refStr << endl;
return retStr;
}
[snip]

RiMZ

ASKER

Can you clear up what you typed it looks as though you have 2 different sets of code to be placed in the if (Members.size() == 2) section...............

if (Members.size() == 2)
{
string retStr = FindMin(Members[0].getKey(key), Members[1].getKey(key));
if (level == 0)
cout << refStr << endl;
return retStr;
}

and

if (Members.size() == 2)
{
return FindMin(Members[0].getKey(key), Members[1].getKey(key), level+1);
}

Also it looks like you are adding level to both FindMin (above) and MinimumObject

******************************************

string MinimumObject(vector<Associate> &Members, string key, int level)
{
string retStr;
vector<Associate> Members2;

if (Members.size() == 0)
return "NULL";

if (Members.size() == 1)
{
string retStr = Members[0].getKey(key);
if (level == 0)
cout << retStr << endl;
}
return retStr;

if (Members.size() == 2)
{
string retStr = FindMin(Members[0].getKey(key), Members[1].getKey(key));
if (level == 0)
cout << retStr << endl;
return retStr;
}

else
{
Members2 = split(Members); // Split Members vector
return FindMin(MinimumObject(Members, key, level+1), MinimumObject(Members2, key, level+1));
}
}

*******************
As the code is above, there is no output when the program is run.
But I saw that for if (Members.size() == 1) you have the return ouside the } if it is placed inside; The function returns a value, but it's the same value as before, it's not the smallest.

Member_2_1001466

When I wrote the first part adding the level parameter I had not thought about the changes later. The importatnt part of the first lines of code are the added parameter which is incremented in subsequent calls of MinimumObject ();

In the second part of the code I added what I thought is needed. But it might be wrong:

Try the following:
string MinimumObject(vector<Associate> &Members, string key, int level)
{
string retStr;
vector<Associate> Members2;

if (Members.size() == 0)
return "NULL";

if (Members.size() == 1)
{
retStr = Members[0].getKey(key);
}

if (Members.size() == 2)
{
retStr = FindMin(Members[0].getKey(key), Members[1].getKey(key));
}

else
{
Members2 = split(Members); // Split Members vector
retStr = FindMin(MinimumObject(Members, key, level+1), MinimumObject(Members2, key, level+1));
}

if (level == 0)
cout << retStr << endl;

return retStr;
}

My error was that in the first call the most likely case to go is more then 2 members. Which finally returns from a call to
MinimumObject () with only 1 or 2 members left.

Does it work like this?

RiMZ

ASKER

I can't follow the logic why but the FindMid function displays the smallest value if I cout each comparison.

string FindMin(string a, string b)
{
bool first = (a<=b);
if (first)
{
      cout<<a<<" is less than "<<b<<endl;
      return a;
}
else
{
      cout<<b<<" is less than "<<a<<endl;
      return b;
}
}

I get a list though because its runing over and over agin. And even though the last comparison is the smallest if I try to ouput the function from main by typing

      string hold;
      hold = Senate_Class.MinimumObject(Senate_Class.Members, "phone", 0);
      cout<<hold<<endl;

It prints a different number (not the smallest)

RiMZ

ASKER

That code doesn't seem to do anything.
There is no output at all even from the FindMin Function.

You realize that there are two different functions here right.... FindMin which compares 2 strings and the recursive function MinimumObject. I ask because you are not consistent with where you are adding the level parameter

RiMZ

ASKER

Should I repost the question again and put the points to 500 to get more people involved?

Member_2_1001466

To the last question: you can increase the number of points up to 500 without reposting it.

I haven't looked in that detail, but for recursion the last comparison performed is not necessarily the one finding the smallest element. But it seems that it should be in this case.

I hoped to have the level function added only to MinmumObject calls. Independent whether these are alone or in a FindMin call.

My idea is you call

MinmumObject (all members, "phone", 0)

in the case of 2 members it calls

FindMin (first member key, second member key)
since level is 0 it should cout the value of this comparison.

in the case of 4 members it calls
split members
FindMin (
MinimumObject (1+2 member, key, 1),
MinimumObject (3+4 member, key, 1)
);

In those calls to MinimumObject no output happens since level is 1 (>0). But they return something to FindMin and FindMin then returns the desired value.

Sys_Prog

I think there is some problem with these part

1. vector<Associate> Members2;

AND

2. if (Members.size() == 1)
{
return Members[0].getKey(key);
}

if (Members.size() == 2)
{
return FindMin(Members[0].getKey(key), Members[1].getKey(key));
}

First of all, what is Associate type like, give some details

What is key, give some details

ASKER CERTIFIED SOLUTION

_ys_

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial