Home arrow Practices arrow Page 10 - Solving Problems with Recursion

Two More Tips - 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!

TABLE OF CONTENTS:
  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
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

So, is this the end of story? Certainly not! There is room for improvement, but that's really beyond the scope of this article. I will just give you 2 pointers. First, the value() function could be greatly enhanced, so that it gives a better scoring system. For example it should give some score for 3 in a row (because that's close to getting 4 in a row). If further studies are made about the game, we can even create a much better value function that takes into account the position of pieces relative to each other, and to the edges and so onů

On the other hand, we can also improve on the bestMove() function itself, by using the alpha beta pruning technique. This technique makes minimax run a lot faster, and I mean a lot. Sadly, this is also outside the scope of this article, but you will find references to alpha beta pruning at the end. Maybe this should be the topic of a future article. Drop me an email if you are interested.

One last comment. The routine we made ignores the case when the board gets full and the game ends in a draw. I didn't want to complicate things, but I am sure you can easily add it to the current code without much trouble.

So, that was it. Our last example for recursion. But this not the end of the journey. The journey has just started. Hopefully you are ready to start writing your own recursive code now.

When to Use (or Avoid) Recursion

As we saw with the flood fill program, sometimes recursion wastes a lot of memory space (or execution time). Other times, recursion is just the way to go. How do you decide?

  1. If the problem definition fits well with a recursive solution, this is a good sign to use recursion, but see number 2.

  2. Before writing a recursive solution, think of memory and processing time. If you can find a non-recursive solution the does the job faster, or by using less memory, don't use recursion (unless you know what you're doing).

  3. Recursion can be overused, resulting in some very clumsy code. Don't overuse recursion, or your code will be unreadable.

  4. If the recursive solution is really small and elegant, this is a good sign you should go for recursion.

  5. Tail recursion (a recursive function whose last line is a recursive call) is optimized well by the compiler. It will not waste memory as you would think.

Finally a bit of theory, for theory fans. Every recursive program can be re-written in a non-recursive way. Period. But this simple statement doesn't indicate how complicated the non-recursive code can be. Sometimes a 3 liner recursive code can become truly monstrous code when you switch into the non-recursive version. It is always your decision.

Your feedback is always welcome. Send me an email (msaad@themagicseal.com), and tell me what you think. I certainly would love to hear from you.

Further Reading



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

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PRACTICES ARTICLES

- 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: