Solved

Output the last run of a recursive function???

Posted on 2003-11-11
19
322 Views
Last Modified: 2010-04-02
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;
            }
}
0
Comment
Question by:RiMZ
  • 8
  • 5
  • 4
  • +2
19 Comments
 
LVL 48

Expert Comment

by:AlexFM
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

by:RiMZ
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

by:Sys_Prog
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

by:RiMZ
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

by:Sys_Prog
ID: 9730037
Check if your list is getting splitted properly

0
 

Author Comment

by:RiMZ
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

by:SteH
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

by:Sys_Prog
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

by:Sys_Prog
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
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 

Author Comment

by:RiMZ
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

by:SteH
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

by:RiMZ
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

by:SteH
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

by:RiMZ
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

by:RiMZ
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

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

Expert Comment

by:SteH
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

by:Sys_Prog
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

by:
_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

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

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…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
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.

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now