Segmentation fault when using recursion function

Question

I'm quite new to programming and for my Object Oriented class (in C++), we have a 2d array with random groupings of "X". I have to use a recursive function to find the different groupings and clear them. As of right now, I check if the spot is an X, clear it, then check the 8 positions around it (including diagonals), and if one of the positions in an X, I call the function again but on that location. My idea is that if I find one X, I will be able to get all the X's around it in one go, thus, I can count it as a group when I find an X.

At the end of the function, I basically loop through all the spots and call the recursive function again if there is another X. However, I keep getting segmentation faults and I'm not sure why. Any help would be greatly appreciated!


void  Recurssive(string Array[][72],int Pos1, int Pos2)
{

int One=1;
int Two=1;
//cout<<"Test 2";
if(Array[Pos1][Pos2]=="X")
        {
        Array[Pos1][Pos2]="0";
        if(Array[Pos1+1][Pos2]=="X")
                {
                Recurssive(Array,Pos1+1,Pos2);
                }
         if(Array[Pos1-1][Pos2]=="X")
                {
                Recurssive(Array,Pos1-1,Pos2);
                }
         if(Array[Pos1][Pos2+1]=="X")
                {
                Recurssive(Array,Pos1,Pos2+1);
                }
         if(Array[Pos1][Pos2-1]=="X")
                {
                Recurssive(Array,Pos1,Pos2-1);
                }
         if(Array[Pos1+1][Pos2+1]=="X")
                {
                Recurssive(Array,Pos1+1,Pos2+1);
                }
         if(Array[Pos1-1][Pos2-1]=="X")
                {
                Recurssive(Array,Pos1-1,Pos2-1);
                }
         if(Array[Pos1+1][Pos2-1]=="X")
                {
                Recurssive(Array,Pos1+1,Pos2-1);
                }
         if(Array[Pos1-1][Pos2+1]=="X")
                {
                Recurssive(Array,Pos1-1,Pos2+1);
                }

        }

for(int i=1;i<22;i++)
        {
        for(int j=1;j<72;j++)
                {
                if(Array[i][j]=="X")
                        {
                        Recurssive(Array,i,j);
                        }
                }
        }


}

Here is the output of the array I am looping through

            X                                                         
             X                                                        
              X           XXXXXXXXXXXXXXX                             
               X          XXXXXXXXXXXXXXX                             
                X         XXXXXXXXXXXXXXX        XXXX                 
                 XXXX     XXXXXXXXXXXXXXX      XXX  XXX               
                     X                        XXX    XXX              
     XXXXXXXXXXXXXX   X                      XXX      XXX             
     XX          XX    X                      XXX    XXX              
     XX          XX     X                      XXX  XXX               
     XX          XX      X                       XXXX                 
     XX  XXXXX   XX       X                                           
     XX          XX        X                                          
     XX          XX         X                                         
     XXXXXXXXXXXXXX          X                                        
                                          X                           
                                         X                            
                                        X                             
                                       X                              
                                      X

This sounds like a great exercise for getting to know your debugger. It will allow you to step through the code and figure out what happens. I suggest trying it on an empty board with just two spots marked with X. — Botje
– Botje, Commented Feb 12, 2020 at 14:47
Your for allows for j to be up to 71, while in the Recurssive function it can be called with j+1 (thus going out of the range for the array). It is the same for i — Hawky
– Hawky, Commented Feb 12, 2020 at 14:48
When j = 71, you are accessing 72nd index in f(Array[Pos1][Pos2+1]=="X"), which is access out of bounds, due to arrays being 0-based. Don't know, if the same can be said for the i index, due to lacking minimal reproducible example (hence - not knowing both of the dimensions of the array), but suspect that it has the same issue. — Algirdas Preidžius
– Algirdas Preidžius, Commented Feb 12, 2020 at 14:49
@Hawky "It is the same for i" Technically - one cannot be certain that it's the same for i, due to the fact, that this dimension of the array is not shown in the question. One can only guess, that it might be an issue. — Algirdas Preidžius
– Algirdas Preidžius, Commented Feb 12, 2020 at 14:52
Thank you for your comments! I made the loop go to 21 and 71, however, it still throws the same error? — Gilbert22
– Gilbert22, Commented Feb 12, 2020 at 14:53

Botje · Accepted Answer · 2020-02-12 15:46:58Z

1

Let's play computer and go through the motions for Recurssive(Array, 0, 0). If this position was marked as X, this will make the following array accesses, in order:

Array[1][0]
Array[-1][0]
Array[0][1]
Array[0][-1]
Array[1][1]
Array[-1][-1]
Array[1][-1]
Array[-1][1]

These -1 accesses will go outside the memory defined by Array and may read a random value or may cause a segmentation fault.

In order to fix this, you need to verify that a candidate position is inside the board before you actually access it. Something like:

std::optional<std::string> safe_access(std::string Array[][72], int Pos1, int Pos2) {
  if (Pos1 < 0 || Pos1 >= 71) return {};
  if (Pos2 < 0 || Pos1 >= 21) return {};
  return Array[Pos1][Pos2];
}

You can then call safe_access(Array, -1, -1) == "X" and be guaranteed this will not access outside of Array.

answered Feb 12, 2020 at 15:46

Botje

32.2k4 gold badges36 silver badges47 bronze badges

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

1 Comment

Gilbert22 Over a year ago

Yes, that was it! Thank you so much!

Collectives™ on Stack Overflow

Segmentation fault when using recursion function

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related