Thread: fill optimizations

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    50

    fill optimizations

    I have the following recursive implementation of the fill algorithm:

    Code:
    void fill(int x, int y)
    {		
    	if ( mat[x][y] == 0 )
            {
    	        mat[x][y] = 1;
    		fill(x+1, y);
    		fill(x-1, y);
    		fill(x, y+1);
    		fill(x, y-1);
    	}
    }
    I'm wondering, is this efficient? I read that the recursion doesn't slow things down in this case as much as it does in other algorithms, is this true?

    Would an interative approach give a significant increase in speed? Is it worth implementing it iteratively, and if so, how would I approach that?

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    you don't check bounds
    you use global variable (are you sure you need it?)
    recursion does not slow things down only if it is optimized by compiler...
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,659
    > I'm wondering, is this efficient?
    No. It uses stupid amounts of stack space for even simple shapes.

    Do a web search for "scanline fill algorithm".
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list fill the gaps question..
    By transgalactic2 in forum C Programming
    Replies: 2
    Last Post: 07-06-2009, 12:35 PM
  2. Question On how to Fill icmp_data
    By Antigloss in forum Linux Programming
    Replies: 3
    Last Post: 04-25-2007, 09:42 PM
  3. Replies: 0
    Last Post: 03-23-2006, 12:42 PM
  4. Quick fill question
    By Mr Moe in forum C++ Programming
    Replies: 5
    Last Post: 02-25-2005, 04:26 PM
  5. Replies: 3
    Last Post: 12-22-2004, 07:29 PM