Recursion First

I’ve long had mixed feelings about recursion. (I’ve written about recursion several times in this blog.) In one post, Recursion Early, Recursion Late, I wrote about the suggestion that recursion be dropped from a first programming or computer science course. In another post I asked if it should be added to a list of Four Key Concepts of Computer Programming. Well recently over dinner a colleague stated that students learn recursion better if they learn it before they learn loops. A second colleague responded that they had seen the same thing. Apparently they both feel that students have to unlearn something if they learn loops before recursion. I have to wonder if that is the reason I struggled with recursion as a student.

Honestly I am not a fan of using recursion for looping. Recursion feels like a resource intensive way to do things that don’t really require it. On the other hand educators I know who start with functional languages such as Scheme tell me that recursion is very natural and easy to learn/use if taught first. This is probably true – that recursion is more natural in functional languages. I remember a time when “does the language support recursion” was a reasonable question that was often answered in the negative. So there was a time when many of us didn’t see recursion as all that practical. I can’t imagine a language today getting far without support for recursion.

Which brings me back to where I started. Recursion has a lot of similarity with “normal” loops. One needs to set the initial state(s), do some sort of work, and setup an properly terminating condition and test. Recursive routines without a clean and clear end state to start the unrolling create huge memory problems and stack overflows. Poorly constructed loops generally either terminate early or never terminate at all. Either way you get an interesting debugging problem. So given all that perhaps it does make sense to start with recursion.

One final note, the colleague who started this conversation told us that she had taught this course twice in a row. The first group of students really took to recursion and tended to use it when other sorts of loops would be as easy or easier to use. The second group complained asking why they had to learn the hard way (recursion) first when loops were so much easier. So you never know how students are going to respond.

So do you teach recursive loops first or some other types of loops first? What works for you?

Comments

• Anonymous
  August 14, 2012
  Teach it when it matters.  If you (1) teach loops for repetition and then (2) introduce recursion without problems (that matter to the students) and (for which recursion isn't better than a loop), then students learn first to distrust recursion. Arrays and lists are so naturally processed with loops that you really need to think about when recursion will click with your students.  Some mathematical problems make recursion sing, and non-linear data structures do, too.  Language processing with a simple grammar can be done in CS1, too.

• Anonymous
  August 14, 2012
  I haven't taught introductory programming, but I've thought about this issue in the process of writing a popular science book on computing for lay readers (<i>Computing for Ordinary Mortals</i>, Oxford, in press). It was hard to decide where recursion should go, but in the end it turned to be natural to describe trees, then to explain how trees can be thought of in recursive terms, and then to make the jump to recursive algorithms. The first example I give (before we get to programming) is how "A journey of a thousand miles begins with a single step" can be expressed either as an iterative procedure or as a recursive procedure.

• Anonymous
  August 16, 2012
  The comment has been removed