TITLE: Recursive Discussions about Recursion
AUTHOR: Eugene Wallingford
DATE: April 24, 2012  4:55 PM
DESC: 
-----
BODY:
The SIGCSE listserv has erupted today with its
seemingly annual discussion of teaching recursion.
I wrote about one of the previous discussions
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2010-07.html#e2010-07-28T14_26_05.htm">
   a couple of years ago</A>.
This year's conversation has actually included a
couple of nice ideas, so it was worth following
along.

Along the way, one prof commented on an approach he
has seen used to introduce students to recursion,
often in a data structures course.  First you cover
factorial, gcd, and the Fibonacci sequence.  Then
you cover the Towers of Hanoi and binary search.
Unfortunately, such an approach is all too common.
The poster's wistful analysis:

<BLOCKQUOTE><EM>
Of the five problems, only one (binary search) is a
problem students might actually want to solve.  Only
two (Fibonacci and Hanoi) are substantially clearer
in recursive than iterative form, and both of them
take exponential time.  In other words, recursion is
a confusing way to solve problems you don't care
about, extremely slowly.

Which, frankly, I think is the lesson [some CS profs]
want to convey.
</EM></BLOCKQUOTE>

And this on a day when I talked with my compiler
students about how a compiler can transform many
recursive programs into iterative ones, and even
eliminate the cost of a non-recursive function call
when it is in a tail position.

The quoted passage contains my favorite line of the
week thus far: <B>In other words, recursion is a
confusing way to solve problems you don't care about,
extremely slowly</B>.  If that's not the message you
want to convey to your students, then please don't
introduce them to recursion in this way.  If that
<EM>is</EM> the message you want to send to your
students, then I am sad for you, but mostly for your
students.

I sometimes wonder about the experiences that some
computer scientists bring to the classroom.  It only
takes a little language processing to grok the value
of recursion.  And a data structures course is a
perfectly good place for students to see and do a
little language processing.  Syntax, abstract or not,
is a great computer science example of trees.  And
students get to learn a little more CS to boot!
-----