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 couple of years ago. 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:
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.
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: In other words, recursion is a confusing way to solve problems you don't care about, extremely slowly. 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 is 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! -----