1

I have been learning about recursions and i did get the concept as to how they work and how to code them.Now,normal recursions are easy to visualize but when recursions involve loops they are totally baffling.

Let's head to the question first,Suppose,i have a string and i have to find possible no of Valid IP addresses that can be generated with that string.

Example

11211

Possible IP addresses

1.1.2.11
1.1.21.1
1.12.1.1
11.2.1.1

I tried to achieve this with something like the given code

vector<string> v;
string period(string str,int i){
    size_t pos=str.find_last_of(".");
    if(pos==string::npos)
        str.insert(i+1,".");
    else
        str.insert(pos+2,".");
    v.push_back(str);
    return str;
}

void recursion(string str){
    for(int i=0;i<=2;i++)
        {
            cout<<i<<'\n';
            string strx=period(str,i);
            if(count(strx.begin(),strx.end(),'.')<4)
                recursion(str);
        }
}
bool validIPaddress(string str){
    //return true for valid ip address
}
int main () {
    string str("11211");
    recursion(str);
    for(vector<string>::iterator it=v.begin();it!=v.end();++it){
    if(validIPaddress(*it))
        cout<<*it<<'\n';
  }
}

enter image description here

I have made a picture of what i am trying to do with my logic.

Try every possible place where i can put my . in between strings and keep that every possible combination inside a vector which has been declared globally as well as don't put more than 3 periods inside a string.

After the recursion finishes ,i have every possible combination using periods and i can just loop through that vector and find the ones that are valid.

Now , the problem is that when i try to implement this logic , my output is not as i expected it to be.I tried to debug my code and get a glance over what have i been doing wrong but i am getting nowhere.

How can i achieve the solution of above problem using recursions?

Regards,

BOTJr.

Improve this question
13
  • When recursive() calls itself, it passes the same value that it received. So it will recurse infinitely. Commented Sep 26, 2016 at 19:39
  • @Barmar no it ain't recursing infinitely, i would have seen , if it has been recursing forever. Commented Sep 26, 2016 at 19:41
  • 2
    "Now , the problem is that when i try to implement this logic , my output is not as i expected it to be." In what way? You didn't give any insight into what the apparent problem is. Commented Sep 26, 2016 at 19:44
  • Recursive algorithms have two parts: 1) Test whether you've reached the base case, and return; or 2) call the function itself with a modified value that should get closer to the base case. I don't see either of them in your code. Commented Sep 26, 2016 at 19:44
  • 1
    It's not infinitely recursing, because your program possibly reached the reserved stack size and did an overflow. But eventually this algorithm should run infinitely if you had infinite memory. What's your return value after program termination? Commented Sep 26, 2016 at 19:45

2 Answers 2

Reset to default
2

Your idea is totally fine, you just shouldn't use a loop. Usually we don't use loops, when we deal with recursive functions. Actually, this problem doesn't involve loops, you just have to recall the recursive function two times.

Your problem is that every loop will call your function again, which means three more iterations. Every iteration will mean three more iterations again, which will be called infinitely. Also, you save every string in the vector, but it's enough to save the correct ones. Since we need to know where to put the next period, we will add a new position argument to the recursive function.

First we have to add the period to the intended position.

void recursion(const string& str, const size_t i = 1){
    //Create a copy of the constant string
    string strx = str;
    //The insert method will insert one dot before the
    //i positioned character in the string
    strx.insert(i, 1, '.');

    //...

After this one period is inserted, we just have to recall this function, but only if there is place for a new period, or we don't have the 3 needed periods.

    //...
    if(count(strx.begin(), strx.end(), '.') < 3)
    {
        //If the count of periods in the new string is under three,
        //then we need to add a new period.
        if (i < strx.size() - 2) recursion(strx, i + 2);
    }
    else
    {
        //The else means, the number of periods if greater or equal
        //to 3. Actually, the only possibility is the equality, so
        //we can add the string to the vector
        v.push_back(strx);
    }

    //Also, we call the recursion on the unmodified string, which means
    //we will get IP numbers starting with two numbers too.
    if (i < str.size() - 1) recursion(str, i + 1); //recall on original
}

In this way, you don't have to call the check function at the end. Note, that we check the length (or size) - 2 at the first recall, because we don't want to get 1..12.11 for instance.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

@BOTJr. No, I'm not at computer right now. If it's not working, tell me, and I'll check it tomorrow morning.
it's throwng an exception .
@BOTJr. Okay, it's my mistake, I didn't read carefully the period function. I'll rewrite my answer.
I have not checked this one if it's working or not.Could you show me a cpp fiddle or something ? i would accept this as the right answer.Furthermore, i wrote something ,you can see that as well.I ain't answering mine as the right one.I just wanted to post it cause, this was the modification of the code present in the question.
Here it is, @BOTJr.: [This](cpp.sh/25p3f) link might not live forever, but you can check it out working. It generates the possibilities, you only have to check, if it's valid for an IP address.
1

I have made some changes according to my question.I have used maps but vectors can be used as well.

Further, ValidIPaddress function considers the basic checks for an IP address,However it doesn't check for checks such as the octals lying in the range 0-255.

map<string,string> v;
bool validIPaddress(string);
string period(string str,int i){
size_t pos=str.find_last_of(".");
if(pos==string::npos)
    str.insert(i+1,".");
else
    if(pos+i+2<=str.length())
         str.insert(pos+i+2,".");
    else return "terminate";

    if(validIPaddress(str))
         v[str]=str;
    return str;
}

void recursion(string str){
        if(str!="terminate")
        {
            if(count(str.begin(),str.end(),'.')<3)
            {
              string other=str;
              for(int i=0;i<=2;i++)
                {
                    recursion(period(str,i));
                    str=other;
                }

            }

        }

}
bool validIPaddress(string str){
 int periods_used=count(str.begin(),str.end(),'.');
   if(periods_used!=3)
        return false;

   size_t pos=str.find_last_of('.');
   if(str.substr(pos+1).length()<1)
     return false;

   int i=0;
   while(i<3)
   {
       int found=str.find('.');
       string strx=str.substr(0,found);
       if(strx.length()<1 || strx.length()>3)
          return false;
       str=str.substr(found+1);
       i++;
   }
    return true;
}
int main () {
string str("11211");
if(str.length()>=4)
   recursion(str);
else
{
    cout<<"No possible IP addresses can be generated."<<'\n';
    exit(1);
}
for(map<string,string>::iterator it=v.begin();it!=v.end();++it)
     cout<<it->first<<'\n';
}

Output:

1.1.2.11
1.1.21.1
1.12.1.1
11.2.1.1
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.