Solved

# Output the last run of a recursive function???

Posted on 2003-11-11
331 Views
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.

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;
}
}
0
Question by:RiMZ
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 8
• 5
• 4
• +2

LVL 48

Expert Comment

ID: 9729297
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).
0

Author Comment

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

LVL 10

Expert Comment

ID: 9729664
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
0

Author Comment

ID: 9729907
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
0

LVL 10

Expert Comment

ID: 9730037
Check if your list is getting splitted properly

0

Author Comment

ID: 9730230
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
0

LVL 13

Expert Comment

ID: 9730242
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.
0

LVL 10

Expert Comment

ID: 9730289
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
0

LVL 10

Expert Comment

ID: 9730351
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
0

Author Comment

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

Any ideas on how to change the recursive function?
0

LVL 13

Expert Comment

ID: 9730408
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]

0

Author Comment

ID: 9730510
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.
0

LVL 13

Expert Comment

ID: 9730544
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?

0

Author Comment

ID: 9730554
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)

0

Author Comment

ID: 9730606
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
0

Author Comment

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

LVL 13

Expert Comment

ID: 9730932
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.
0

LVL 10

Expert Comment

ID: 9730940
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

0

LVL 9

Accepted Solution

_ys_ earned 250 total points
ID: 9731745
RiMZ,

As a solution was provided in your subsequent post, what are you going to do with this one ... delete it.

Subsequent post:
http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_20795422.html
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why tâ€¦
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the bâ€¦
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor anâ€¦
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
###### Suggested Courses
Course of the Month6 days, 4 hours left to enroll