On Apr 14, 2005, at 21:06, [EMAIL PROTECTED] 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?"
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
