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.
-----