I am reading a table of numbers into an array then calling a recursive function. My program works great for small numbers like 4, 5, 6 but when I read in the 22 by 22 table, I get a segmentation fault:
"unhandled exception: stack overflow"
Why does the program work for small numbers and not large numbers and how do I fix it?
The problem happens in the following function:
void trace(int count, int loc, bool marker, int col[COLS],
int row[ROWS], int table[ROWS][COLS], int size)
{
count++;
if(marker)
{
for(int x = 0; x < size; x++)
{
if(table[loc][x] == 1)
{
col[x] = count;
trace(count, x, false, col, row, table, size);
}
}
}
else
{
for(int x = 0; x < size; x++)
{
if(table[x][loc] == -1)
{
row[x] = count;
trace(count, x, true, col, row, table, size);
}
}
}
return;
}
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
The problem is not only due to recursive process (which person1994 says does not end) i think its because the since you are passing parameters by value...so they are adding up to the stack everytime the function is called that fills up the stack....try changing the stack frame i.e try changing the Memory model you are using to compile the code...make it to HUGE...maybe things will get better....
hope that helps
cryptosid
As person1994 said and peterdownes illustrated, you have a problem in that under the right circumstances your recursion will never end and your stack will blow up.
In your algorithm (as best I can describe it) you do a column-major search for a value of 1. Upon finding it you will then perform a row-major search in the same row where you found the 1, this time looking for -1. If you don't find a -1 you will go back to the previous column and look for the next 1.
Data as simple as:
1 -1
-1 1
Will recurse forever - well until the stack runs out.
If you think of each of the 1's and -1's as opposite corners of a square you will see the problem at any point that you have a sub-square within your data that has 1's at one pair of diagonal corners and -1 at the other.
if you take 4 values to represent the corners of any given square (anywhere within your table):
x
y
m
n
val[x][y] = val[m][n] = 1 and val[m][y] = val[x][n] = -1
or
val[x][y] = val[m][n] = -1 and val[m][y] = val[x][n] = 1
Will equal infinite recursion. This is the simple case.
It becomes more difficult for me to describe when you get to different shapes. Suffice to say that - at any point that the you have a "circular path" you will be in trouble.
So, to handle your problem. You need to have two exit conditions from your recursive loop. You have the one for the situation where the path just ends - i.e. you don't find a -1 in the row you are searching or you don't find a 1 in the column you are searching. You need another to exit if you find yourself back where you started.
You can accomplish this by having static variables say colFirst and rowFirst that hold the initial hit (the row, column where you found -1)
static int colFirst = -1;
static int rowFirst = -1;
// == -1 before the recursive call to trace()
if (colFirst != loc || rowFirst != x)
{
if(!count)
{
colFirst = loc
rowFirst = x
}
col[x] = count;
trace(count, x, false, col, row, table, size)
}
You will have to do something with count since you have that as your lead in line of code so you don't count the same location twice so ...
else
{
--count;
}
Since I am only guessing at what you are trying to do - some sort of node count along a path or finding the longest path in a graph - I can't tell whether or not you really intend to continue counting along all possible paths from a given column or whether you want to count each path independently. If the latter is true then you will need to reset count back to the value you stored prior to each recursive trace() call. In the == -1 part you would need:
trace()
count = col[x];
and in the == 1
trace()
count = row[x]
Like I said, I am only guessing but ask more questions or supply some more information to clarify what needs to be done.
Business Accounts
Answer for Membership
by: peterdownesPosted on 2002-10-24 at 21:07:30ID: 7367993
Could you show us where you call this.