Home arrow Practices arrow Page 5 - Solving Problems with Recursion

How it Works - Practices

Recursion is a way to solve a problem by...reducing it to the same problem. What? It may be counterintuitive, but many turn-based games (including chess) use exactly this technique to make a computer player "think." Mohamed Saad explains the concept, along with when (and when not) to use recursion in your programming. Check out the Connect4 example!

  1. Solving Problems with Recursion
  2. The Plot Thickens
  3. First Programming Example
  4. The Flood Fill Algorithm
  5. How it Works
  6. Connect 4 AI program
  7. The Minimax Method
  8. Placing Pieces
  9. Trying it Out
  10. Two More Tips
By: Mohamed Saad
Rating: starstarstarstarstar / 54
November 17, 2004

print this article



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.

Solving Problems with Recursion

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. 

>>> More Practices Articles          >>> More By Mohamed Saad

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort


- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates


Dev Shed Tutorial Topics: