HomePractices 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!
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.
Contains a C source code to do the non-recursive version of flood fill. It certainly uses less memory, but look how long the code became. (Just for the sake of comparison).
/ 54 
