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?