[The comments below were written specifically about the TeachScheme! approach to teaching recursion, about which you can read more in the textbook. But they apply to the whole curriculum.]
There are two down-sides to our approach.
First, it forces the teacher to move away from stupid, unmotivated but "safe" examples like factorial and fibonacci. There's a safety to using bad examples, which is that everyone else is using them -- the "nobody got fired for recommending an IBM product" theory. Our teachers have to defend why they're doing something innovative. We hope not too many of you are running into this problem.
Second, it lets us get into much deeper material much more quickly. Students get upset that their course is so much harder than that of, say, their high school buddy at another university. In some cases, people suffer an utter inversion of priorities. One of our colleagues at Caltech wrote that a student in the Scheme-based [first-semester] course there filed the following complaint. The student wrote:
I just talked to a friend at a neighboring university and he showed me a 3rd-semester homework assignment which he considered hard, and it was totally trivial.
(In case it's not clear on first reading, the student is complaining that what his friend got to take 3 semesters to learn, and even then as a challenge problem, he was expected to be able to do in just one. And this is a Caltech student! Read and weep.)
-- Shriram Krishnamurthi
Here's another way to look at this. In a typical CS1 course, students spend most of their time compiling, reading a syntax error message, fixing it, compiling again, reading another syntax error message, fixing it, etc. All of this time they can tell themselves they are "making progress", perhaps even "learning something", when in fact they're just wasting hours on mindless drill. In the TeachScheme! approach, students are expected to think and design the program, following principles of programming rather than by trial and error and the seats of their pants. This is harder work, and students don't like it.
Of course, TeachScheme! students produce a correct program much more quickly, but then they don't get to enjoy their vacation -- we make them go on to another, more sophisticated concept that the C++ or Java student wouldn't be expected to learn at all in the first year. They don't like this either.
-- Stephen Bloch, inspired by something Matthias Felleisen wrote
Or as Helene Martin wrote after attending a TeachScheme! workshop,
"the signal to noise ratio in functional programming is very high. In other words, programs are generally quite short, but every line requires deliberate thought."