I want to apologize to everyone who read the post I put in the other thread about when and why to use recurrsion. I said never use it because it is stupid and only makes you look smart. Well last night I found a reason to use it. I couldnt think of a way to do it in a for loop (if there even is one). I used it for a floodfill if you are familiar with what that is. It is like when you are using MSPaint and you draw a very irregular picture on the screen with the pencil. And you choose the bucket and fill it with a color. That is floodfill. Now I was thinking of a way to do this in my program, and recursion was the solution. It looks like this in 8 bit mode

    
// pitch already equals the pitch of the surface

// surface is a LPDIRECTDRAWSURFACE4

// surfptr is a pointer to the surface data

// height is height of the surface

// width is width of the surface


floodfill(int x, int y, BYTE newColor)
{
// lock the surface here

  BYTE startColor = surfptr[x + y*pitch];
  floodfillHelper(x, y, startColor, newColor);
// unlock surface here

}

floodfillHelper(int x, int y, BYTE startColor, BYTE newColor)
{
// if it isnt the starting color, which is the color being changed FROM then return
  if (surfptr[x + y*pitch] != startColor)
    return;
// if it is already the newcolor then return

  if (startColor == newColor)
    return;
// set to new color

  surfptr[x + y*pitch] = newColor;
// call recursively for surrounding four pixels

  if (y > 0)
    floodfillHelper(x, y-1, startColor, newColor);
  if (y < height - 1)
    floodfillHelper(x, y+1, startColor, newColor);
  if (x > 0)
    floodfillHelper(x-1, y, startColor, newColor);
  if (x < width - 1)
    floodfillHelper(x+1, y, startColor, newColor);
}
    

I am sure this has been thought of before and is probably how everything and everyone does it but I did think it up for myself and was quite happy. And my aplogies to everyone who had to read my post about recurrsion being crap "Now go away or I shall taunt you a second time" - Monty Python and the Holy Grail themGames Productions

Congratulations!
You have found well-known & the slowest algorithm for FloodFill.

quote: Original post by Serge K

Congratulations!
You have found well-known & the slowest algorithm for FloodFill.

So does that mean tha recurssion is pointless? I''ve never been able to fully understand recursion.

Aha! I feel useful.

Recursion is just calling a function within itself, eg:

Function(void)
{
Function();
}

I beleive that that is all it is. (By the way, that would be an endless loop up there. Stupid compiler doesn''t catch it.........

PPL: Correct me if I''m wrong.

Dare wa neko o koroshiteimasuka? (Ha! Learn Nihongo!)

To say that recursion is useless is simply demonstrating your own ignorance. Just try to implement any kind of tree-based data structure without recursion. You''ll end up implementing your own stack which is simply emulating recursive function calls, and won''t be any faster - it''ll just make your code a thousand times more complicated to code, more prone to bugs, and difficult to read and debug.

-RWarden (roberte@maui.net)

That can easily be done without using recursion. Just implement stack or queue by yourself and put every new starting coordinate into that stack/queue. Then you just pop those values one at time...

Somthing like this :

do{
coord=popValueFromStack();

if(nextCoordIsOkay)pushValueToStack(nextCoord);
if(anotherNextCoordIsOkay)pushValueToStack(anotherNextCoord);

if(stackIsEmpty)end=true;
}while(!end);

I just did that with 3D voxels. Wouldn''t have worked with recursion because of limited stack size.

-Ratsia

quote: Original post by Ratsia

Just implement stack or queue by yourself and put every new starting coordinate into that stack/queue. Then you just pop those values one at time...

[..snip....]

Wouldn''t have worked with recursion because of limited stack size.

You''re not really saying anything new here. No-one said recursion had to be used for everything, just that it works well in certain circumstances. Sure, it can always be replaced by iteration, if you''re willing to go to the effort of reimplementing features that are already at your disposal, such as the stack, just like you can always replace C++ with assembly if you were so inclined. The fact is, recursion is useful in certain contexts, especially when performing a function across many members of a tree-like data structure which is already defined in a recursive sense.

I know it''s nothing special. I only replied because ncsu121978 (what kind of username is that?-) said that he/she couldn''t think of a way to do it without recursion.

I myself use recursion when it seem like the best solution. I have nothing against it.

-Ratsia

You could do everything without recursion (without a function which calls itself) and Abrash writes in the Black Book you shouldn''t write recursive functions because function calls are slow. And it''s not too difficult to write e.g. a non-recursive walk through a binary tree (there''s an example in the Black Book and I had no problems to write the code for walking through a tree where each node has a variable number of subnodes). However, I don''t know if it''s still faster to use non-recursive algorithms on systems with new CPUs, I think function calls don''t cost that much time on modern computers.

GA

ok, SergeK (or anyone else), how would you do floodfill ? Remember this is on predrawn bitmaps where you dont know any of the vertices. For all you are concerned it doesnt have vertices.
It is just a very irregular shape.
I''m not saying there is not an easier and faster way to do it but I just dont know what it is. I have read how to do polygon filling, but that wont work here because in polygon filling, you need to know the vertices of the polygon.
And my username is from the college I go to and my birthday


"Now go away or I shall taunt you a second time"
- Monty Python and the Holy Grail
themGames Productions