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!
Whew, and that's it. Now we have a nice Connect 4 AI engine that can actually look several moves ahead, thanks to recursion. For example, if we try the engine on this position:
Fig 4.The AI (red player), will know how to win in this situation
If the program is called to play for the red player with a depth of only 3, it will correctly find that the best move is to put a piece in column 2 to force the human to block at column 5 and then the computer wins by putting a piece at column 5.
In another situation:
Fig 5.If the computer (yellow player) could only see one step ahead, he would be unable to see the threat of playing at column 3 or 6 and winning. Now, it can detect and prevent it.
The computer correctly decides to play at column 3 to block the human from winning by putting at column 3 or 6.
Pretty impressive, huh? And it is all less than 30 lines of code.