Recursion

I think one of the biggest mistakes in teaching recursion is going into it as if students are going to have a tough time grasping it. My experience is that most students find it intuitive - unless I make a big deal of it, in which case they adjust their expectations of themselves downward.

Examples I don't like

Almost every textbook uses these examples, and many use only these examples. But they're bad examples: It's not obvious to students why they should care about them, they don't represent the cases where recursion is useful, and recursion is the wrong way to address the problems anyway.

• factorial function

• Fibonacci numbers

• Towers of Hanoi

The only one of these examples that I recommend at all is the Fibonacci numbers - and then only for the purpose of demonstrating recursion trees. (I generally teach students how to draw recursion trees since I think they need a way of visualizing the process.)

Examples I like

There aren't many good examples of recursion that can be used in an introductory class, so I'm always on the lookout for more. Here are the ones that I think are worth mentioning.

• Printing numbers in an arbitrary base. For example, maybe we want a method to display an int in octal format.

• Simple fractals, particularly the Sierpinski gasket. While it's just a pretty picture, many students like it. And it is a useful visualization of recursion.

• Flood fill / Minesweeper / Maze. These are all the same problem, in different guises.
  • Flood fill: Paint programs frequently have a "paint bucket" tool for recoloring all adjacent pixels with the same color. Write an algorithm to do this.

  • Minesweeper: When the user clicks a space with 0 mines, all connected spaces with 0 mines are automatically clicked.

  • Maze: Find a route from start to finish in a maze. (This guise is slightly tricker than the others, because it requires "bread crumbs" that the other scenarios have automatically built in.)

• Tree traversal / directory searching. Trees are a particularly rich source of recursion. Of course, trees aren't formally a topic in the CS A exam; but a useful related scenario that students will easily grasp is searching a directory and all its descendants for a file of a particular name. This could even be an assignment using java.io's File class.

• 8-queens problem: Write a program to discover an arrangement of eight queens on a chessboard that can't attack each other. This is a standard textbook example with no obvious applications, but it is at least a search problem, and searching is a major application for recursion.

• Subset sum. I like to describe this as the ``jewelry thief'' problem: Suppose we break into a store with a lot of gold merchandise, but our bag can only carry a particular amount. For example, maybe there are pieces weighing 5, 15, 20, 23, and 40 pounds, and we can only carry 44 pounds out. Write a program to decide which pieces to put into the bag.

• Prefix expression evaluation. We want to evaluate mathematical expressions where operators are written before the operands, as in ``+ 2 3'' to represent ``2 + 3'' or ``* 2 - 3 4'' to represent ``2 * (3 - 4)''.

  When/if students figure this out, they'll be impressed by how elegant the solution is, and it will sell them on recursion. Only the brightest students will be able to handle it, though, for it's a bit tricky.

(schedule)