Segmentation fault in C++ recursive function

Question

The problem is to delete adjacent pair of identical alphabets until there is no such pair. I have used recursion for this. But the code gives Segmentation fault. What is wrong with this recursion?

#include<iostream>
#include<string>
using namespace std;
string super(string s)
{
        for(int i=0;i<s.length();i++)
        {
                if(s[i]==s[i+1])
                {
                        s.erase(s.begin()+i);
                        s.erase(s.begin()+i+1);
                        s=super(s);
                        cout<<s;
                        break;
                }
                if(i+1==s.length())
                        return s;
        }
        return s;
}
int main()
{
        string s;
        cin>>s;
        s=super(s);
        if(s.length()<0)
                cout<<s;
        else
                cout<<"Empty String";
}

Consider that you are dereferencing i and i+1. For simplicity sake, what if the string only had a single character in it? — AndyG
– AndyG, Commented May 8, 2018 at 12:43
fyi: when you get it working you might want to change if(s.length()<0) cout<<s; — Richard Critten
– Richard Critten, Commented May 8, 2018 at 12:49
Note that after s.erase(s.begin() + i), the character that used to be as s.begin() + i + 1 is now at s.begin() + i. — Pete Becker
– Pete Becker, Commented May 8, 2018 at 12:49
The same thing happened when I switched the order of for loops — Bavya
– Bavya, Commented May 8, 2018 at 12:52

Aaron Pool · Accepted Answer · 2018-05-08 12:51:14Z

4

Your conditional checks are out of order, s[s.length()] will, by definition, cause a segmentation fault, so you need to make sure i+1 is less than the length of s BEFORE you attempt to access it.

Right now you're accessing s[i+1], and THEN checking if i+1 < s.length().

answered May 8, 2018 at 12:51

Aaron Pool

4892 silver badges6 bronze badges

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

Comments

ZekeMarsh · Accepted Answer · 2018-05-08 12:52:56Z

0

You are indexing out of range. if i == s.length()-1 (which is the last character's index), then your s[i+1] will be out of range.

Also just in general the logic is flawed because you will restart the operation from the beginning each time you encounter matching. If you have 'abccba' I assume you would want 'abcba', however your code would return abca. The time complexity of your solution is less than ideal. This could be done in linear time.

In the last line you want s.length() > 0 (or you could just use s.empty()).

answered May 8, 2018 at 12:52

ZekeMarsh

12210 bronze badges

Comments

Fabio · Accepted Answer · 2018-05-08 14:25:09Z

0

From what i understood peoples hate comments in code so i will reapeat them here on the top of the answer:

Well first of all in the for cicle, for not going out of index you have to start from 1 and ceck if the i-1 and i position of the string are equal.

Second you can simply erase from the i - 1 position to the i + 1 position.

Lastly when you want print the sting in the main you have to ceck if the length of the string is not empty, the length can't be < 0

And on top of that just calling the method inside himself doesn't make it a "recursive solution", the code below is an iterative solution for your problem

#include<iostream>
#include<string>
using namespace std;
string super(string s){
        for(int i=1;i<s.length();i++)                                 // you start from 1 to doesn't go out of bound
                if (s[i-1]==s[i])
                        s.erase(s.begin() + (--i), s.begin() + i + 1);// you decrease i and erase from i decreased to i + 1
        return s;
}
int main(){
        string s;
        cin>>s;
        s = super(s);
        cout << ((s.length())? s : "Empty String");                    // the string is empty if the lenght is not 0, you have to change < with >
        return 0;
}

This instead is a recursive solution, you can see the disappearance of the for cycle (is not wrong use cycles but is easy to do wrong using them)

#include<iostream>
#include<string>
using namespace std;
string super(string s, int i){
    if (i < s.length()){
        if (s[i-1]==s[i]){
            s.erase(s.begin() + i - 1, s.begin() + i + 1);
            s = super(s, i);
        }
        else
            s = super(s, i + 1);
    }
    return s;
}
int main(){
    string s;
    cin>>s;
    s = super(s, 1);    //from input the size can't be 0 so give 1 is ok
    cout << ((s.length())? s : "Empty String");
    return 0;
}

edited May 8, 2018 at 14:25

answered May 8, 2018 at 13:11

Fabio

3133 silver badges14 bronze badges

4 Comments

AndyG Over a year ago

Code only answers are discouraged. Please elaborate on the code and why you wrote it the way you did as compared to OPs code.

Fabio Over a year ago

There are comments in that explain the change

463035818_is_not_an_ai Over a year ago

not sure about others, but I tend to completely ignore comments in code. also most of them are hidden behind the scrollbar.

463035818_is_not_an_ai Over a year ago

...well if i use the scrollbar I can read the comments but dont see the code :-(

Collectives™ on Stack Overflow

Segmentation fault in C++ recursive function

3 Answers 3

Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related