Thread: ::please help with recursion::

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    13

    ::please help with recursion::

    I know there are a lot of people with enough experience to help figure out how to debug the last problem with my program.
    the problem is when you enter the starting coordinates as shown it can't fill in the whole "image" leaving out a small portion. Does anyone have any suggestions on how to get this program to function with any starting point without leaving out anything?
    Also this was one of my first attempts at writing a recursive program so any advice would be appreciated.

    code posted below:

    Code:
    #include <iostream>
    
    //function: to simulate the paint bucket function to fill in an area of an "image"
    //          specifically using recursion.
    
    //written by: justin mortensen
    //date: 08/15/05
    
    using namespace std;
    const int rows = 10;
    const int col = 15;
    
    //example "image" for testing
    
    char image[rows][col]= {
         {'.','.','.','.','.','X','X','.','.','.','.','.','.','.','.'}, //0
         {'.','.','.','.','X','.','.','X','X','.','.','.','.','.','.'}, //1
         {'.','.','.','.','X','.','.','.','.','X','X','X','X','.','.'}, //2
         {'.','.','.','X','.','.','.','.','.','.','.','.','X','X','X'}, //3
         {'.','.','X','.','.','.','.','.','.','.','.','.','.','.','.'}, //4
         {'.','.','.','X','.','.','.','.','.','.','.','.','X','X','.'}, //5
         {'.','.','.','X','.','.','X','X','X','.','.','.','X','.','X'}, //6
         {'.','.','.','X','.','.','X','.','.','X','.','X','.','.','.'}, //7
         {'.','.','.','X','X','X','X','.','.','.','X','.','.','.','.'}, //8
         {'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.'}  //9
    };
    
    // function prototypes
    void printImage();
    void AreaFill(int x, int y);
    void AreaFill_helperLD(int x, int y); //Left and down
    void AreaFill_helperRD(int x, int y); //Righ and down
    void AreaFill_helperUL(int x, int y); //Up and left
    void AreaFill_helperUR(int x, int y); //Up and right
    
    
    int main () 
    {
     printImage();
     cout << endl;
     AreaFill(6,9); //putting these coordinates at the start doesn't fill
     printImage();  //        in the whole "imag"
    
     cin.get();
     return 0;
    }
    
    //function to fill the image 
    void AreaFill(int x, int y) {
    AreaFill_helperLD(x,y);
    AreaFill_helperRD(x,y);
    AreaFill_helperUL(x,y);
    AreaFill_helperUR(x,y);
    
    }
    
    
    void AreaFill_helperLD(int x, int y) {
         if (image[x][y] == 'X') {
            return;
         }  
         else if (x > rows - 1) {
              return;
         }
         else if (x < 0) {
              return;
         }
         else if (y > col - 1) {
              return;
         }    
         else if (y < 0) {
              return;
         }
         else {
              image[x][y] = '0';
              AreaFill_helperLD((x+1),(y));
              AreaFill_helperLD((x),(y-1));
              
         }
    
    }
    
    void AreaFill_helperRD(int x, int y) {
              if (image[x][y] == 'X') {
            return;
         }  
         else if (x > rows - 1) {
              return;
         }
         else if (x < 0) {
              return;
         }
         else if (y > col - 1) {
              return;
         }    
         else if (y < 0) {
              return;
         }
         else {
              image[x][y] = '0';
              AreaFill_helperRD((x),(y+1));
              AreaFill_helperRD((x+1),(y));
         }
    
    }
    
    void AreaFill_helperUL(int x, int y) {
              if (image[x][y] == 'X') {
            return;
         }  
         else if (x > rows - 1) {
              return;
         }
         else if (x < 0) {
              return;
         }
         else if (y > col - 1) {
              return;
         }    
         else if (y < 0) {
              return;
         }
         else {
              image[x][y] = '0';
              AreaFill_helperUL((x-1),(y));
              AreaFill_helperUL((x),(y-1)); 
         }
    
    }
    
    void AreaFill_helperUR(int x, int y) {
              if (image[x][y] == 'X') {
            return;
         }  
         else if (x > rows - 1) {
              return;
         }
         else if (x < 0) {
              return;
         }
         else if (y > col - 1) {
              return;
         }    
         else if (y < 0) {
              return;
         }
         else {
              image[x][y] = '0';
              AreaFill_helperUR((x),(y+1));
              AreaFill_helperUR((x-1),(y));  
         }
    
    }
    
    void printImage() {
         int i = 0;
         while( i < 10) {
         for (int j = 0; j < 15; j++) {
             cout << image[i][j];
         }
         cout << endl;
         i++;
         }
    }

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    125
    Seems to me that if you want a fool-proof filling algorhythm you'd be better off with one recursing function that goes in 4 directions, rather than 4 functions that each go in 2 directions. That would give a much easier to read program as well.
    It would result in an ungodly amount of recursions for a sizable image though, so you'll probably have to take a bit of a smarter approach. (for example having one call to the function fill a whole horizontal line as opposed to just one pixel; filling a horizontal line could be done with a while-loop instead of recursion)
    Another thing, rather than checking for whether a byte is filled with 'X', it might be better if you instead check whether it's NOT filled with '.' or even better: whatever the value of your starting byte was. (you could pass this as an argument of the recursive function as well)
    That way you could fill any area of one value.
    Typing stuff in Code::Blocks 8.02, compiling stuff with MinGW 3.4.5.

  3. #3
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    well, you can use my code to see what's going on there:
    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    void printImage();
    void areaFill(int x,int y);
    inline void clearScreen() { system("clear"); }
    void wait();
    
    char image[10][15]= {
         {'.','.','.','.','.','X','X','.','.','.','.','.','.','.','.'}, //0
         {'.','.','.','.','X','.','.','X','X','.','.','.','.','.','.'}, //1
         {'.','.','.','.','X','.','.','.','.','X','X','X','X','.','.'}, //2
         {'.','.','.','X','.','.','.','.','.','.','.','.','X','X','X'}, //3
         {'.','.','X','.','.','.','.','.','.','.','.','.','.','.','.'}, //4
         {'.','.','.','X','.','.','.','.','.','.','.','.','X','X','.'}, //5
         {'.','.','.','X','.','.','X','X','X','.','.','.','X','.','X'}, //6
         {'.','.','.','X','.','.','X','.','.','X','.','X','.','.','.'}, //7
         {'.','.','.','X','X','X','X','.','.','.','X','.','.','.','.'}, //8
         {'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.'}};  //9
    
    int main()
    {
    	clearScreen();
    	printImage();
    	std::cout<<std::endl;
    	areaFill(6,9);
    	std::cout<<std::endl;
    	return 0;
    }
    
    void printImage()
    {
    	for(register int y=0;y<11;y++)
    	{
    		for(register int x=0;x<16;x++)
    		{
    			std::cout<<image[y][x];
    		}
    		std::cout<<std::endl;
    	}
    }
    
    void areaFill(int x,int y)
    {
    	if(image[x][y]=='X')
    	{
    		return;
    	}
    	image[x][y]='X';
    	wait();
    	clearScreen();
    	printImage();
    	if(x-1>0)
    	{
    		areaFill(x-1,y);
    	}
    	if(y-1>0)
    	{
    		areaFill(x,y-1);
    	}
    	if(x+1<16)
    	{
    		areaFill(x+1,y);
    	}
    	if(y+1<11 && x+1<16)
    	{
    		areaFill(x+1,y+1);
    	}
    }
    
    void wait()
    {
    	time_t start=clock();
    	while(clock()-start<500){}
    }
    basically, it's drawing itself into a box and doesn't know to get out of it... if you watch closely, you'll see that it blocks itself off. the algorithm is working right, just not the way you expected.

    edit: you may need to change "clear" at the top to "cls" if you're using windows
    edit2: if you're using this for any production-level thing, I'd find a replacement for the wait() and clearScreen() functions I've provided - the wait() function eats up processor time, and clearScreen() uses some possibly dangerous code.
    Last edited by major_small; 08-16-2005 at 07:20 AM. Reason: color-happy syntax highlighter,see edit.
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  4. #4
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    okay... I found out what was wrong (at least with my code). the X and Y vertices were getting mixed up. here's a bit of (semi) working code:
    Code:
    //for console I/O
    #include <iostream>
    //for system (find replacement)
    #include <cstdlib>
    //for timing code (find replacement)
    #include <ctime>
    
    //draws the image
    void drawImage();
    //fills a little and redraws image
    void areaFill(int x,int y);
    //clears the screen (find replacement)
    inline void clearScreen() { system("clear"); }
    //timing code (find replacement)
    void wait();
    
    //the map (try to de-globalize this)
    char image[10][15]= {
         {'.','.','.','.','.','X','X','.','.','.','.','.','.','.','.'}, //0
         {'.','.','.','.','X','.','.','X','X','.','.','.','.','.','.'}, //1
         {'.','.','.','.','X','.','.','.','.','X','X','X','X','.','.'}, //2
         {'.','.','.','X','.','.','.','.','.','.','.','.','X','X','X'}, //3
         {'.','.','X','.','.','.','.','.','.','.','.','.','.','.','X'}, //4
         {'.','.','.','X','.','.','.','.','.','.','.','.','X','X','X'}, //5
         {'.','.','.','X','.','.','X','X','X','.','.','.','X','.','X'}, //6
         {'.','.','.','X','.','.','X','.','.','X','.','X','.','.','.'}, //7
         {'.','.','.','X','X','X','X','.','.','.','X','.','.','.','.'}, //8
         {'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.'}};  //9
    
    int main()
    {
    	//clear the screen
    	clearScreen();
    	//draw the initial image
    	drawImage();
    	//fill it in (and draw it)
    	areaFill(9,6);
    	//flush the stream
    	std::cout<<std::endl;
    	//end the program
    	return 0;
    }
    
    //draws the image
    void drawImage()
    {
    	//loop through the rows
    	for(register int y=0;y<11;y++)
    	{
    		//loop through the columns
    		for(register int x=0;x<16;x++)
    		{
    			//print the colums
    			std::cout<<image[y][x];
    		}
    		//print the rows
    		std::cout<<std::endl;
    	}
    }
    
    //fill in the area
    void areaFill(int x,int y)
    {
    	//if this is already filled
    	if(image[y][x]=='X')
    	{
    		//return
    		return;
    	}
    	//if not, fill in the area
    	image[y][x]='X';
    	//add a little pause
    	wait();
    	//clear the screen
    	clearScreen();
    	//re-draw the image
    	drawImage();
    	//if there's space left west
    	if(x-1>-1)
    	{
    		//send a spider that way
    		areaFill(x-1,y);
    	}
    	//if there's space left south
    	if(y-1>-1)
    	{
    		//send a spider that way
    		areaFill(x,y-1);
    	}
    	//if there's space left east
    	if(x+1<16)
    	{
    		//send a spider that way
    		areaFill(x+1,y);
    	}
    	//if there's space to the north
    	if(y+1<11)
    	{
    		//send a spider that way
    		areaFill(x,y+1);
    	}
    }
    
    //timing code - find a replacement
    void wait()
    {
    	//get the time
    	time_t start=clock();
    	//loop until about 500 miliseconds have passed
    	while(clock()-start<500);
    }
    I say semi working because there's some problems with writing the image... you'll see.

    edit: I found the problem... it's a n00bish problem, so I'm not gonna help you out with it other than telling you that it occurs in two places, and requires four changes.

    edit2: this would look so much cooler if you used multiple threads
    Last edited by major_small; 08-16-2005 at 08:01 AM.
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  5. #5
    Registered User
    Join Date
    Aug 2005
    Posts
    13
    Thank you both Boksha and major_small for taking the time to look at my code and give me some advice. If this wasn't an exercise just to practice recursion I would probably prefer to use loops just to fill it in instead of so many recursive calls but I wanted to try my hand at using recursion and I can see where I need to improve Thank you major_small for providing that last example of code it was really helpful in teaching me some tricks on slowing down the recursion so i could examine how it was working that was something i wished i had known before how to implement for debugging also your code was what i had in mind at first in order to solve the problem but I missed some little things when i first wrote it and then my version that i posted was what I had to resort to in order to get it functioning correctly. I am right now studying your code to see where the n00b problem is because I hope that it will help me with debugging in the future. But I hope that if i can't see it you wouldn't mind maybe giving me a hint. Also since I don't know much about threads maybe you could explain a little about how they would help implement the areaFill function?

    edit: oh just figured out that your draw() function was accessing past the array elements, fixed that and it works like a charm, cheers
    Last edited by daioyayubi; 08-17-2005 at 01:56 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM