[Tutor] Re: Recursion....what are the best situations to use it?

[Max Noel]

On Apr 14, 2005, at 21:06, jsoares at Safe-mail.net wrote:

> I've seen a couple of nice tutorials on recursion, and a lot of awful 
> ones. The latter always trot out the fibonacci and factorial examples 
> for some reason. And that's about it! The good ones showed me how to 
> trace through recursive calls and gave me practical 
> examples(tictactoe, magic squares, Tower of Hanoi, 4-Square, etc)
>
> What I want to know is this: what are other specific situations where 
> a recursive algorithm would be better or easier to program than an 
> iterative one?

	Heh. This is perhaps one of the few times where Microsoft makes 
something easy to explain. If you've used Windows 2.0 or later, chances 
are you've seen an excellent example of recursive programming: the 
world's second-most used productivity application, Minesweeper.

	In Minesweeper, when you click on a tile that doesn't contain a mine, 
the number of mines in adjacent tiles appears. But you've probably seen 
that if there are no mines in any of the adjacent tiles, the program 
explores all the "safe zone" instead of letting you click on all those 
empty tiles. That is recursion.

	The way it does that is as follows (this is simplified pseudocode, 
which doesn't take into account edges, among other things):


def explore(minefield, (y, x)):
     numMines = countSurroundingMines(minefield, (y, x))
     minefield[(y, x)] = EXPLORED
     if numMines == 0:
         for i in ((y-1, x), (y+1, x), (y, x-1), (y, x+1)):
             if minefield[i] != EXPLORED:
                 explore(minefield, i)


	Voilà. Aside from the GUI and this piece of code, writing an 
implementation of the Windows Minesweeper is perfectly trivial. In 
fact, I did just that a few years ago on my dear TI-92 to learn how to 
use recursion. You should do the same if you've got a few hours of 
spare time, it's an enlightening experience. ^^

-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
"Look at you hacker... A pathetic creature of meat and bone, panting 
and sweating as you run through my corridors... How can you challenge a 
perfect, immortal machine?"