Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition.That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a good idea, but telling them that it's a familiar idea that they already implicitly understand isn't a good idea either. The way people normally conceive of iterative processes does not contain the essential element of recursion: that something is used in its own definition. The recursive definition of eating a bowl of Cheerios is: if there are Cheerios in the bowl, you're done; otherwise, spoon some Cheerios into your mouth and then eat the bowl of Cheerios. Most people encountering recursion in a class have never thought that way before. (Jokes are perhaps the only counterexample, though I can't think of any right now.)
That doesn't mean it's hopeless. As another poster said, recursion isn't difficult. It's a simple idea. It's just different. "Different" has big consequences, though. In interviews, I give candidates a programming problem that is solvable using recursion. Very few people come close to solving it -- mostly I judge people by how they approach the problem, not whether they eventually figure out the solution -- but usually, after figuring out (perhaps with lots of prompting) that the problem can't be solved with nested for loops, they manage to volunteer the word "recursion."
Now here's the kicker: about half the candidates who say they're going to solve the problem "recursively" do not actually attempt a recursive solution, not even an incorrect one. They seem to associate recursion with defining functions, because they begin their "recursive" solution by defining a function. However, they do not define a function that calls itself. They do not define mutually recursive functions, either. These are applicants for a senior technical position. They aren't washouts, they're people who have had years of development experience at some point in their careers.
If half the people who are technically inclined enough to choose a career in development, stick with it for many years, and advance to a senior position have a hard time with recursion.... No, if those people don't even understand the basic idea behind one of the most famous concepts in their field (a concept whose name they can still recall despite never or rarely needing to use it since college) then it is not a way of thinking that people develop outside of math and computer science. It isn't a skill that people naturally apply in other domains but have a hard time applying to programming. It isn't just a problem of making a connection between the word "recursion" and a cognitive skill that everybody has. No, it's an alien way of thinking that only becomes familiar through sufficient practice. Until it becomes a natural way of thinking, it's just a definition that can be forgotten as easily as forgetting the year the Magna Carta was signed.
Iterative solutions do follow familiar thinking patterns. Write a sentence on the chalkboard 100 times. Chop on the tree until the tree falls down. Check every line in your credit card statement. Let's drink every one of these bottles of beer. When students write a program that has a for loop or a while loop, they're expressing something familiar they've done countless times before. They're just doing it in a new and unfamiliar form. Even many of the common constructs in functional programs have been drilled into kids since grade school. Map: examine every child's head for lice. Filter: make a list of everyone who didn't turn in their permission slip. Those ways of thinking are thoroughly ingrained, and students who drop CS 101 and become art history majors won't forget how to think that way just because they don't write programs.
Teaching kids recursion before iterative constructs might be a good idea on balance, but let me play devil's advocate. Teaching iterative constructs first has one big advantage: while the students are grappling with the novelty of describing a process in the form of code, at least they are describing familiar processes they understand. Teaching them recursion first means they will be trying to learn the mechanics of writing a program at the same time they're trying to learn recursion. When they have difficulties, they might not be able to figure out which concept they're getting wrong. Why not teach them to program iterative constructions first, and then, after they have some confidence with the task of writing a complex program in a programming language, let them tackle the challenge of recursion? That way they always have something familiar to lean on while they're struggling.
I sympathize with the basic motivation whenever anyone proposes teaching recursion before iteration, which is to keep the kids dependent on their skill with recursion. As soon as they figure out that for and while loops are sufficient to express all the programming ideas they can come up with, they won't want to learn anything else. If recursion is their only tool for expressing simple programs, they'll keep struggling with it until they learn it. Unfortunately, that's not going to work. Kids have always been able to read ahead in the book, and now the first place they'll look is the internet, where other students will let the cat out of the bag. You're going to have to persuade them that it's worth struggling with until they understand it.