This talk describes a method for teaching recursion to intro-level students that the presenter has now been using for 3 semesters in his introductory CS labs, initially for students who were not successfully engaged by existing materials, and now as part of the standard materials on the topic. Notably, the method does NOT require any wishful thinking on the part of the student, and the presenter has found it to be anecdotally quite successful in allowing students who are stuck to solve recursive problems they had asked for help with. The method should work equally well for teaching induction.

To summarize the method: first, define your base case. Next, pretend that you will be writing an infinite number of cases one-by-one, and write the “base + 1” case, without recursion. Continue to write cases, eventually introducing recursion, but only into cases that you have already defined. Finally, write a generalized recursive case based on the patterns you have observed, and then remove redundant cases. As noted above, at no point except in the very end do students have to “assume it will work” for previous cases, and by the end, they are more comfortable doing that as they’ve shown through a few examples why this is true.

Students must still be able to both identify the base case, and identify the sequence of cases that are relevant. For complex recursive problems where, e.g., recursion proceeds until a minimum length is reached, this method is more difficult.