Solving Problems with Recursion - Two More Tips
(Page 10 of 10 )
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?
- If the problem definition fits well with a recursive solution, this is a good sign to use recursion, but see number 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).
- Recursion can be overused, resulting in some very clumsy code. Don't overuse recursion, or your code will be unreadable.
- If the recursive solution is really small and elegant, this is a good sign you should go for recursion.
- 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
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
/ 33 
