Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function )

This thread had mentioned helping students understand recursion, and
for some reason, this topic of understanding recursion has come up a
lot lately "by the water cooler", among other things.

I recently heard that a particular teacher quit trying to teach
recursion because "it is too hard for students to understand".

Is there an epidemic of sorts that students don't understand recursion?

What are the challenges to understanding recursion?