TITLE: Sending Bad Signals about Recursion AUTHOR: Eugene Wallingford DATE: July 28, 2010 2:26 PM DESC: ----- BODY: A couple of weeks ago there was a sustained thread on the SIGCSE mailing list on the topic of teaching recursion. Many people expressed strongly held opinions, though most of those were not applicable outside the poster's own context. Only a few of the views expressed were supported by educational research. My biggest take-away from the discussion was this: I can understand why CS students at so many schools have a bad impression of recursion. Like so many students I encounter, the faculty who responded expressed admiration for the "beauty and elegance" of recursion but seemed to misunderstand at a fundamental level how to use it as a practical tool. The discussion took a brief side excursion into the merits of Towers of Hanoi as a useful example for teaching recursion to students in the first year. It is simple and easy for students to understand, said the proponents, so that makes it useful. In my early years of teaching CS1/CS2, I used Towers as an example, but long ago I came to believe that real problems are more compelling and provide richer context for learning. (My good friend Owen Astrachan has been sounding the clarion call on this topic for a few years now, including a direct dig on the Towers of Hanoi!) My concern with the Towers is more specific when we talk about recursion. One poster remarked that this problem helped students to see that recursion can be slow:

Recursion *is* slow if you're solving a problem that is exponentially hard like Hanoi. You can't solve it faster than the recursive solution, so I think Hanoi is a perfectly fine example of recursion.

This, I think, is one of the attitudes that gives our students an unduly bad impression of recursion, because it confounds problem and solution. Most students leave their first-year courses thinking that recursion is slow and computationally expensive. This is in part an effect of the kinds of problems we solve with recursion there. The first examples we show students of loops tend not to solve exponentially hard problems. This leads students to infer that loops are fast and recursion is slow, when the computational complexity was a feature of the problems, not the solutions. A loop-based solution to Towers would be slow and use a lot of space, too! We can always tell our students about the distinction, but they see so few examples of recursion that they are surely left with a misimpression, through no fault of their own. Another poster commented that he had once been a consultant on a project at a nuclear reactor. One of the programmers proudly showed one of their programs that used recursion to solve one of their problems. By using recursion, they had been able to construct a straightforward inductive proof of the code's correctness. The poster chided the programmer, because the code was able to overflow the run-time stack and fail during execution. He encouraged them to re-write the code using a subset of looping constructs that enables proofs over the limited set of programs it generates. Recursion cannot be used in real-time systems, he asserted, for just this reason. Now, I don't want run-time errors in the code that runs our nuclear reactors or any other real-time system, for that matter, but that conclusion is a long jump from the data. I wrote to this faculty member off-list and asked whether the programming language in question forbids, allows, or requires the compiler to optimize recursive code or, more specifically, tail calls. With tail call optimization, a compiler can convert a large class of recursive functions to a non-recursive run-time implementation. This means that the programmer could have both a convincing inductive proof of the code's correctness and a guarantee that the run-time stack will never grow beyond the initial stack frame. The answer was, yes, this is allowed, and the standard compilers provide this as an option. But he wasn't interested in discussing the idea further. Recursion is not suitable for real-time systems, and that's that. It's hard to imagine students developing a deep appreciation for recursion when their teachers believe that recursion is inappropriate independent of any evidence otherwise. Recursion has strengths and weaknesses, but the only strengths most students seem to learn about are its beauty and its elegance. Those are code words in many students' minds for "impractical" and, when combined with a teacher's general attitude toward the technique, surely limit our students' ability to get recursion. I'm not claiming that it's easy for students to learn recursion, especially in the first year, when we tend to work with data that make it hard to see when recursion really helps. But it's certainly possible to help students move from naive recursive solutions to uses of an accumulator variable that enable tail-recursive implementations. Whether that is a worthwhile endeavor in the first year, given everything else we want to accomplish there, is the real question. It is also the question that underlay the SIGCSE thread. But we need to make sure that our students understand recursion and know how to use it effectively in code before they graduate. It's too powerful a tool to be missing from their skill set when they enter the workforce. As I opened this entry, though, I left the discussion not very hopeful. The general attitude of many instructors may well get in the way of achieving that goal. When confronted with evidence that one of their beliefs is a misconception, too many of them shrugged their shoulders or actively disputed the evidence. The facts interfered with what they already know to be true! There is hope, though. One of Ursula Wolz's messages was my favorite part of the conversation. She described a study she conducted in grad school teaching recursion to middle-schoolers using simple turtle graphics. From the results of that study and her anecdotal experiences teaching recursion to undergrads, she concluded:

Recursion is not HARD. Recursion is accessible when good models of abstraction are present, students are engaged and the teacher has a broad rather than narrow agenda.

Two important ideas stand out of this quote for me. First, students need to have access to good models of abstraction. I think this can be aided by using problems that are rich enough to support abstractions our students can comprehend. Second, the teacher must have a broad agenda, not a narrow one. To me, this agenda includes not only the educational goals for the lesson but also general message that we want to send our students. Even young learners are pretty\ good at sensing what we think about the material we are teaching. If we convey to them that recursion is beautiful, elegant, hard, and not useful, then that's what they will learn. -----