Recursive Functions and Microsoft Minesweeper
Recursive Functions
There are quite a few tutorials on the web about recursive functions - I've even posted one myself - that use the old standby Factorial of 5 explanation. It's a great example and illustrates the concept very well.
OK, fine, so we can use recursive functions to do factorials, but there are calculators and pre-written functions that handle that, so why do I need to understand recursion?
Opening game
After first move
What might help is another less common real-world example. Let's take a look at Microsoft's® standby game, Minesweeper®. It's a game that most people are at least somewhat familiar with. This quick tutorial will hopefully help you see how recursion works in the code behind this great little game.
Minesweeper starts it's beginner game with a 9x9 grid of squares. When the user clicks on the center square (red "X"), the program must look at all 8 adjacent squares (in yellow) and determine how many mines surround that square. It happens that no matter where you click first, the eight surrounding squares will not contain mines. It's just the way the game is programmed. Live with it. However, many of those squares may have one or more mines surrounding them. Now we begin to get recursive...
Here's how it works:
The eight squares surrounding the red "X" each have squares surrounding them. Each one of them must be examined in turn to see how many mines surround them. In the case of our example, the square directly below the red "X" had zero mines surrounding it. Now the program must check each of the squares surrounding that square.
So... first we must have a function that checks surrounding squares for mines. It could happen that one of the squares we're checking needs to have its surrounding squares checked for mines. The same function that checks adjacent squares for mines needs to include a function call to check adjacent squares for mines - it may need to call itself.
The code is a bit more involved than what we can go into in a short blog, but here is a recap of the concept:
If one started on the square with the black dot, coordinates (5,3) in an (x,y) grid, one would need to check square (4,2) to see if it's a bomb. If it isn't, one would need to see how many bombs surround (4,2), so the program would call itself with new coordinates. This time, the program would check (3,1) to see if it's a bomb. If it isn't, the program would need to see how many bombs surround (3,1), so the program would call itself with new coordinates to check (2,1) to see if it's a bomb. If it IS, it would increment the counter in the stack iteration for (3,1) and move to (4,1) to check to see if it's a bomb. Once all the squares surrounding (3,1) have been checked and all the bombs surrounding it accounted for, we can return a value to the stack iteration for (4,2) and move on to (5,2) which is directly above the black dot and start the whole process over again.
Yes, it's more complex than that, really. A lot of head-scratching went into programming MineSweeper, simple game though it is. It still makes for a good example of how Recursive Functions work and what they can be used for besides finding factorials.
