Solving Problems with Recursion - How it Works
(Page 5 of 10 )
How does this code work? Looks too small to be true? Well, it isn't. It works like this: you start at a point, if it is already colored you do nothing. This condition prevents color from flowing out.
Next, you turn your attention to the 4 neighboring pixels. If any one of them is not colored, start a flood fill from that point too. And guess what, when you start a flood fill from each of those points, they will start to fill the neighboring pixels, and so on, and so on... This is the magic of recursion.
Take a look at this figure. It shows the first 3 steps of how flood fill works. This figure is not actually 100% accurate in terms of the sequence of pixels being filled, but I hope it illustrates the idea.
Fig 3. Starting at the red point, the program fills the point, and then calls itself to fill the 4 surrounding points, and then from each of the surrounding point, calls itself to fill the 4 surrounding each one of them and so on (Note: the function calls will not occur concurrently as shown here. This is just for illustration purpose. In reality. They will be called one after the other. The sequence of coloring pixels will be different)
Now you see how it works. We have created a really nice flood fill algorithm that can fill really complicated shapes with a minimum amount of effort.
I'll let you in on a little secret. The code we have just written is bad in its memory usage. Really bad. Why? The same function is called again for every pixel. Each function call takes a specified amount of memory that is released when the function is finished. And so, by the time we reach the last pixel to fill, there are lots of instances of the flood fill function all in the memory, taking lots of space. For a large shape, this memory could be in the megabytes range. Not something to be ignored if you are working on a machine with limited memory (such as a mobile phone).
The moral is to be careful when dealing with recursion. There is a secret overhead because of the function calls, which should never be ignored.
Coming up next is a major example, and one of the best uses of recursion. It is harder than the previous examples, but it's such a good example that I feel obligated to include it. Grab a cup of coffee; it should help. I'd treat you if I could...but let's not digress. Instead, let's go directly to our final example.
Next: Connect 4 AI program >>
More Practices Articles
More By Mohamed Saad
/ 32 
