It's nice to see Dave Jacobus blogging about his programming courses again. Looks like all of his classes (IB CS, AP CS and Visual Basic) are all learning about recursion lately. Recursion is a really cool concept. I have to admit though that it took me a while to get the hang of. That may be because not to many programming languages really supported recursion back in the old days when I was first learning to program.
Recursion is one of those interesting things that when it is good is really good but when it goes wrong can go horribly wrong. Accidental recursion often leads to the discovery of the stack overflow. I had a student writing one of his first C++ programs have main call itself. You can imagine the result. It allowed for a great class discussion - talk about a teachable moment.
Recursion at its most simple can be little different from any regular iterative routine. In my opinion that is an interesting use for recursion but in some ways it is a waste of its potential. The most interesting uses of recursion are those uses that make it possible or even easy to do things that are otherwise difficult or impossible.
One of my favorite recursive projects was a version of Minesweeper. In Minesweeper when you hit clear locations (a square that doesn't hold or neighbor a mine) the program opens spaces until it locates spaces that do neighbor mines. Checking for those locations iteratively is pretty complex. There may be a good iterative way to do it but I haven't figured out. Doing it recursively though is pretty spiffy.
There are other good recursive projects - traversing a directory structures or similar tree structures, Towers of Hanoi - of course but some of them seem to get old. So I'm always looking for new and interesting recursive projects. Anyone have any to suggest?
I always thought the Logo turtle was great for explaining it with visualizations; a picture being worth a thousand words and all that. It's a great way to show the relation to fractals as well.
I created a version of minesweeeper (in KPL 1.1--its available for download at www.kidsprogramminglanguage.com), and I found that recursion worked, but was far too slow. Plus I hit a stack overflow in the KPL environment for minesweeper boards above 30x30 or so.
My revised solution was a queue: when clearing a square, add the "surrounding squares" to the end of an array. Clear the cells one at a time from the front of the array, and add any additional cells to the end of the array.
This had a view advantages:
* Simple in-memory list instead of a huge call stack
* Worked much faster
* Visually more interesting and more like the original minesweeper app. By this I mean that it clears gradually in all directions like you would expect--the recursion version went "deep first" and looked kind of funny as it cleared.
Wow! What a great solution Brad. I'd never thought of that but it makes a whole lot of sense. Learn something new every day. Thanks!