I just ran into an interesting old post from Eric Lippert about How Not to Teach Recursion. I don’t necessarily agree that calculating Fibonacci numbers is a bad example, but I might have a good one.

When I was a second year CS student I had a crush on a girl. I don’t remember any more, but I think we were already dating then. She asked me to help her with the written exam for the first year programming course. At that time they teach you Pascal as a language and a bit about algorithms in general. So I faked my way in and did the test for her (hey, I was young, stupid and horny).

As a geek, I decided to go with the hardest problem out of four we were presented. This problem carried the most points so I figured if I solve one more she’ll barely pass (I didn’t want to overdo it). The easiest (assuming you’re not afraid of it) way to solve the problem involved recursion.

Here’s the problem: imagine a chess board of arbitrary dimensions. Some of the “positions” are occupied and cannot be used. Your “figurine” is at arbitrary position Xs, Ys and can move only horizontally or vertically to the adjacent positions, unless the new position is occupied. Elsewhere on the board at the position Xt, Yt is a goal. You need to find the shortest path from the start to the goal position.

If there were no occupied positions this could have been solved semi-manually and iteratively. But there are potentially many, so the recursive solution that essentially exhausts all of the possible paths worked just fine.

I’m not sure if this is a good way to teach recursion, but it sure is a better motivation example as the backtracking can easily be visualized.