Recursion

Classic minefield is now finished, and I should have the modern version finished next Sunday. Part of the minefield core game revolves around the use of recursion so today I am going to explain the concept behind recursion while using minefield as an example.

In mathematics, a function that calls itself is said to be a recursive function. This technique can also be useful for all sorts of programming problems as long as the function is properly written. The problem with recursion is that a poorly written recursive function can be dangerous. Lets take a look at recursion and how it was used in the Ultimate Retro Projects' minefield games.

In the minefield game, the player has to uncover hexagons which reveal how many nearby hexagons have mines in them. In some cases, there will be hexagons that have no mines near them. In these cases, the player would automatically uncover all the surrounding hexagons, which is a pain. To make the game flow faster, this is automated for the player so that clicking on a hexagon with no mines will automatically uncover the surrounding hexagons. This uncovering of tiles is done in the uncover function by calling the uncover function for each of the surrounding hexagons.

The reason that the uncover function is called instead of just automatically marking the hexagons as uncovered is due to the obvious fact that it is possible that one of the uncovered hexagons may also not have any mines nearby. However, this leads to a potential problems that can cause an infinite recursion to occur. Technically speaking, infinite recursions don't happen in Java because making function calls uses stack memory so the recursion will eventually run out of stack memory causing an exception to occur. The net result is still the program crashing so obviously infinite recursions are something you want to avoid.

The potential problem is that if uncover detects that the hexagon is not near mines, then the surrounding hexagons are uncovered. If one of the uncovered tiles also has no mines, it is going to try and uncover the hexagon that is responsible for uncovering it. This continues back and fourth until the call stack is filled. The solution to this problem is fairly obvious. You simply need to check to see if the tile that is about to be uncovered has already been uncovered If so, immediately return from the function with the uncovered value.

The above example points out the key thing that has to be kept in mind when you are creating a recursive function. You must always make sure that the recursion has a stopping point and that the end of the recursion will always reach this stopping point in a reasonable amount of time. In fact, some people place recursive functions in the same category as self-modifing code and the goto statement and consider it bad. It is always possible to avoid recursion but often recursion is the fastest and easiest way to implement something.