During a discussion on how to teach CS1, one one of my colleagues wrote:
"I introduce things like linked lists very early, because once you've done data structures of any stripe, and then type hierarchies, the idea of a recursive data structure with two variants (empty, and non-empty) is a pretty natural one. Furthermore, it motivates recursion without most of the strangeness that usually entails---you're handing off part of the job to *someone else*, rather than to "yourself". Linked lists serve as data structures of arbitrary size, which let students start writing interesting programs much earlier than otherwise. And using recursion instead of iteration lets you put off teaching mutation (i.e. assignment statements) until relatively late in the course---which is a huge benefit as you don't have to teach the difference between pass-by-value and pass-by-reference in week 2, which you would otherwise have to do. The polymorphic-recursion paradigm also is good at isolating the different pieces of what you have to do than is the iterative model, which seems to be good for building a conceptual framework."
My response:
The real difference between this philosophy and mine here I think is the view of recursion. Of course I think recursion is central to many algorithms and problem solving techniques, but I've never been convinced it should be taught early. I've never agreed that recursion is easy or natural for most people. I've never agreed with the Scheme folks (sorry Abelson, Sussman, Felleisen, et. al) that recursion should be taught from day one and that syntax is evil. (This from someone who spent many years working in Lisp and thinking about machine learning - all recursively, of course.)
That said, what I do think is that folks understand iteration and simple decisions much more easily than they do recursion. I'm a big fan of Boehm & Jacopini's fundamental control structure theorem. I'm also a big fan of not hiding the machine. So I teach assignment early, I teach pre-test iteration early, and I teach conditionals early. I'm not a big fan of IDEs even though I teach them and use them when I have to.
Oh, and I also think that programs with 87 objects in them, 84 of which do pretty much nothing but are there just because you can break something down into smaller pieces, are stupid. But that's my object-oriented programming rant. Don't get me wrong, I think that object-oriented design is a very powerful paradigm and is one of several very good ways of looking at how to solve problems. But I also think that some of it's advocates take it waaaaay too far.
I do like the idea of linked lists early because it frees you from having to talk about limits on data structures at the beginning, but I'm also willing to live with arrays, including arrays of objects, to get halfway there.
This is all probably because I learned programming in the early '70s when "structured programming" was new and because I spent most of my career in industry doing operating system and embedded programming of some form or another in either assembly language or in C. I'm warped - and I like it that way. ;^) I learned procedural programming first, then functional, and then - way later - logic programming (I like Prolog, weird as it is) and object-oriented, so I'm always more comfortable when I return to my roots.
