GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 12-Jan-2009, 10:46
takachi takachi is offline
Awaiting Email Confirmation
 
Join Date: Dec 2007
Posts: 101
takachi is an unknown quantity at this point

A problem with recursion


I've written a program which get's a matrix 10*10 with values of 1 or 0.0 means we can travel to that point and 1 means it's an opsticale.we can move forward,backward,down or up assuming the values of those places are 0's.
the function checks if there's a path between the starting point and the finish point.
this is the function:
CPP / C++ / C Code:
void findPath(int arr[10][10],int begin,int end)
{
        int BI1,BI2; //begin index 1 and begin index 2
        if (begin==end)
        {       arr[0][0]=10;
                return;
        }
        else
        {
                BI2=begin%10;
                BI1=(begin-BI2)/10;
                if (((BI1+1)<=9)&&(arr[BI1+1][BI2]==0))
                        findPath(arr,begin+10,end);
                if (((BI2+1)<=9)&&(arr[BI1][BI2+1]==0))
                        findPath(arr,begin+1,end);
                if (((BI2-1)>=0)&&(arr[BI1][BI2-1]==0))
                        findPath(arr,begin-1,end);
                if (((BI1-1)>=0)&&(arr[BI1-1][BI2]==0))
                        findPath(arr,begin-10,end);
        }
}


and the main function:
CPP / C++ / C Code:
int main()
{
        int arr[10][10],i,j,begin,end;
        printf("Please enter 10*10 zeros or ones:\n");
        for (i=0;i<10;i++)
        {
        for (j=0;j<10;j++)
                    scanf("%d",&arr[i][j]);
    }
    printf("Please enter start point:\n");
        scanf("%d",&begin);
    printf("Please enter end point:\n");
                   scanf("%d",&end);
    findPath(arr,begin,end);
    if (arr[0][0]==10)
       printf("Path exists? Yes\n");
    else
        printf("Path exists? No\n");
        return 0;
}

for some reason I get a segmentation fault.
here's the input
Code:
Please enter 10*10 zeros or ones: 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 Please enter start point: 00 Please enter end point: 10 Segmentation fault (core dumped)

how can I fix it and what causes this error?
  #2  
Old 12-Jan-2009, 13:17
fakepoo fakepoo is offline
Regular Member
 
Join Date: Oct 2007
Posts: 713
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: a problem with recurrsion


For starters, I would put some logging/debug messages in your function so that you can see what it is doing and what step it crashes on. Also, something to think about is that you could be in an endless loop. Maybe you should pass some sort of path (collection...could be a dynamic array and a count) so that you do not go to the same location more than once. Here are my thoughts:

CPP / C++ / C Code:
struct Point
{
  int x;
  int y;
};

struct Path
{ 
  Point* points;
  int numPoints;
};

// return a pointer to a new path object if found, NULL if not
// Note: the calling function must free any memory returned by this function
Path *FindPath( int arr[10][10], Path *path, Point *current, Point *point) // find the point in the path
{
  // Create a copy of path.....we will call it newPath

  // Add current to newPath

  // have we found the point?
  if( current->x == point->x && current->y == point->y ) return newPath;

  // Right
  //  if the right square is a 0 and not on our path already, set current to the right square and call this function with the new path
  //  if it does not return NULL, you are done and should return it

  // Left

  // Up

  // Down

  // If we got here, we did not find the path
  return NULL;
}
 
}
  #3  
Old 12-Jan-2009, 13:30
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 5,218
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: a problem with recurrsion


Quote:
Originally Posted by takachi
...
this is the function...how can I...what causes...

You can instrument the function to see what it is seeing and to see how deep the recursion gets before the program aborts (due to overflow of stack):

CPP / C++ / C Code:
void findPath(int arr[10][10], int begin, int end)
{
    static int depth = 0;
    int BI1, BI2;               /*begin index 1 and begin index 2 */
    printf("In findPath: depth =  %d, begin = %d, end = %d\n", ++depth,begin, end);
    if (begin == end) {
        --depth;
        arr[0][0] = 10;
        return;
    }
    else {
        BI2 = begin % 10;

Regards,

Dave
  #4  
Old 13-Jan-2009, 01:38
takachi takachi is offline
Awaiting Email Confirmation
 
Join Date: Dec 2007
Posts: 101
takachi is an unknown quantity at this point

Re: a problem with recurrsion


thanks to your advice I've figuared whats the problem.it appears that the function makes an endless loop because it moves between 89 to 99 over and over.The solution must be to mark the places I've already been to but the problem is that I may need to return back.
So I have no idea what to do.any help?
  #5  
Old 13-Jan-2009, 08:15
fakepoo fakepoo is offline
Regular Member
 
Join Date: Oct 2007
Posts: 713
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: A problem with recursion


Why would you ever need to return back to a place that you have already been?
  #6  
Old 13-Jan-2009, 08:18
takachi takachi is offline
Awaiting Email Confirmation
 
Join Date: Dec 2007
Posts: 101
takachi is an unknown quantity at this point

Re: A problem with recursion


because if I am found in a point with several availiable directions and I choose one with no end I need to return back and choose a different path.
  #7  
Old 13-Jan-2009, 08:29
fakepoo fakepoo is offline
Regular Member
 
Join Date: Oct 2007
Posts: 713
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: A problem with recursion


Did you read the first post that I made on here? Let me explain it a little bit:

When you go to a point, the function FindPath() branches in ALL FOUR DIRECTIONS assuming that a path has not been found yet. This is what makes recursion so powerful. You can simply tell it to find the path and then you know that it will try every combination of moves to get there until it finds it because you know that it will go in every direction. You also know that it does not need to go back to a previous point because, if it has already been there, it will have gone in all directions from that point. Here is the process:

1) Enter FindPath() with the current point
2) If we are at the end point, then return the path.
3) Try FindPath() up if it is not already on our current path. If it returns a valid path, return it.
4) Try FindPath() down if it is not already on our current path. If it returns a valid path, return it.
5) Try FindPath() right if it is not already on our current path. If it returns a valid path, return it.
6) Try FindPath() left if it is not already on our current path. If it returns a valid path, return it.
7) Since we never found a valid path in any of our directions, return NULL.

Does this make sense to you?
  #8  
Old 13-Jan-2009, 08:59
takachi takachi is offline
Awaiting Email Confirmation
 
Join Date: Dec 2007
Posts: 101
takachi is an unknown quantity at this point

Re: A problem with recursion


so what changes should I make in the code which I've written?
  #9  
Old 13-Jan-2009, 09:11
fakepoo fakepoo is offline
Regular Member
 
Join Date: Oct 2007
Posts: 713
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: A problem with recursion


Try to do what I have shown you. Then, when you think you have something that needs a little tweaking, post your code. It might be easier for you to comment out your code and start from scratch. Look at my first post. I don't think I can make it any more clear without writing the entire program for you.
 
 

Recent GIDBlogToyota - 2009 May Promotion by Nihal

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Torrents Download Problem chandeep Computer Software Forum - Linux 7 09-Oct-2006 23:37
Graphic problem in Unreal Tournament 2004 zerox Computer Software Forum - Games 10 09-Oct-2005 13:31
Runtime Problem involving "printf" in C Program supamakia C Programming Language 2 09-Oct-2005 11:09
a significant problem after installing Xp mohammad Computer Software Forum - Windows 10 09-Aug-2005 08:03

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 21:01.


vBulletin, Copyright © 2000 - 2009, Jelsoft Enterprises Ltd.