Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Run time error in recursive function

Posted on 2004-09-24
1
Medium Priority
?
183 Views
Last Modified: 2010-04-01
Hi there.

I'm writing a program which reads in a boolean grid from a TXT file and finds groups of "true" values called blobs.

It includes a recursive function which finds the size of a blob at any grid point. A run time error occurs in the program and I believe it is due to a mistake in this function, called "getBlobSize".

Here is the source code:

#include <iostream>
#include <cstdlib>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

class grid
{
  // A class which manipulates a 2-dimensional grid of bool
 
   public :
       grid();  
       // default constructor - initialises variables
       void readGrid(string filename);
       // precondition : none
       // postcondition :
       // if a file called filename exists then the file of grid
       // data has been read in
       // otherwise the message  "File does not exist" is
       // displayed
       void printGrid();
       // displays the grid data with each row on a new line
       int getMaxBlob();
       // precondition : isEmpty is false and findAllBlobs has been invoked
       // postcondition : returns the size of the maximum blob
       bool isEmpty();
       // returns true if grid data is empty (not successfully read in)
       // and otherwise false
       void findAllBlobs();
       // precondition : isEmpty is false
       // postcondition : the size of each blob has been determined
       // and displayed (integers separated by tabs)
       // the maximum blob size has been determined.
       
   protected :
       int getBlobSize(int curRow, int curCol);
       // recursive function called by findAllBlobs()
       // returns the size of the current blob
       // (a blob starting at row CurRow and column curCol).

   private :
       vector < vector <bool> >  v;   // the 2-dimensional grid of data
       int rows;                      // the number of rows in the grid data
       int cols;                      // the number of columns in the grid data
       int maxBlob;                   // the size of the maximum blob found
                                      // (set by findAllBlobs())
};    

int main()
{
  grid mainGrid;
  string file;                                      
 
  cout << "Enter filename" << endl;
  cin >> file;                        // type data.txt
  mainGrid.readGrid(file);
 
  if (!mainGrid.isEmpty())
  {
    mainGrid.printGrid();

    mainGrid.findAllBlobs();
 
    cout << "The maximum blob size is " << mainGrid.getMaxBlob() << endl;
  }

  system("PAUSE");
  return 0;
}

grid::grid()
{
  rows = 0;
  cols = 0;
  maxBlob = 0;
}

void grid::readGrid(string filename)
{
  char cell;
 
  ifstream inFile;
 
  inFile.open(filename.c_str());
 
  if (!inFile)
    cout << "File does not exist" << endl;
  else
  {
    inFile >> rows >> cols;
   
    v.resize(rows, vector <bool> (cols, false));
   
    for (int i=0; i < rows; i++)
    {  
      for (int j=0; j < cols; j++)
      {
        inFile >> cell;
       
        if (cell == '*')
        {
          v[i][j] = true;
        }
        else if (cell == '.')
        {
          v[i][j] = false;
        }    
      }
    }    
  }

  inFile.close();  
}

void grid::printGrid()
{
  char cell;
 
  for (int i = 0; i < rows; i++)
  {
    for (int j = 0; j < cols; j++)
    {
      if (v[i][j] == true)
      {
         cell = '*';
      }
      else if (v[i][j] == false)
      {
         cell = '.';
      }  
     
      cout << cell;
    }
   
    cout << endl;
  }
}

int grid::getMaxBlob()
{
  return maxBlob;
}

bool grid::isEmpty()
{
  return v.empty();
}

void grid::findAllBlobs()
{
 
  int curSize = 0;
 
  for (int i=0; i < rows; i++)
  {  
    for (int j=0; j < cols; j++)
    {
      curSize = getBlobSize(i, j);
      if (curSize >= 2) cout << curSize << '\t';
      if (curSize > maxBlob) maxBlob = curSize;
    }
  }
  cout << endl;
}

int grid::getBlobSize(int curRow, int curCol)
{
  // I believe the run time error is caused somewhere in this function
  if (curRow > rows || curRow < 0 || curCol > cols || curCol < 0)
    return 0;
  else if (!v[curRow][curCol]) return 0;
  else
  {
    v[curRow][curCol] = 0;
   
    return 1 + getBlobSize(curRow - 1, curCol)
             + getBlobSize(curRow - 1, curCol + 1)
             + getBlobSize(curRow, curCol + 1)
             + getBlobSize(curRow + 1, curCol + 1)
             + getBlobSize(curRow + 1, curCol)
             + getBlobSize(curRow + 1, curCol - 1)
             + getBlobSize(curRow, curCol - 1)
             + getBlobSize(curRow - 1, curCol - 1);

  }
}

Here is the contents of the data file called "data.txt":

6 8
......*.
.**..*.*
.***..*.
..*.....
....*...
...**...

I've checked the function and can't find the problem. Any thoughts about why this error occurs and possible solutions would be greatly appreciated.

Thankyou.
0
Comment
Question by:Bonescraper
[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
  • Learn & ask questions
1 Comment
 
LVL 13

Accepted Solution

by:
SteH earned 240 total points
ID: 12141379
Most likely you need to return if
 if (curRow >= rows || curRow < 0 || curCol >= cols || curCol < 0)
Indices go from 0 to n-1 if array size is n.
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
Suggested Courses

636 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