This is a topic very close to my heart. I think that the skeptical attitude you've alluded to simply comes from the fact that most people were taught imperative programming first (and some were never exposed to any other paradigms at all). Turing's Machine was easier to conceive of as a physical, mechanical device than Church's $\lambda$, and it is presumably by this historical accident that mutability rules the day almost everywhere.
I am not even remotely convinced that imperative programming is more obvious or intuitive than functional programming. In my experience, setting values is a consistent cognitive trap for students, and one that I have to treat with great care. My very first unit for AP is modeled rather loosely after Tom Rogers' phenomenal opening AP unit, Java Ain't Algebra, which takes exactly this issue head on.
In my (by now heavily modified) version of Roger's mini-unit, I make explicit that values can change, spend time tracing them, show why
x = 4 + 7 is not the same as
x - 4 = 7, and spend a lot of time making clear that the programmer's
is only barely related to the mathematical
We also begin to explore the runtime stack.
Teachers often miss that this even needs to be covered because, once they are thoroughly inculcated in imperative programming, it can become hard to even see why this is hard in the first place. The variable
4, but now it is
5. What could be simpler?
But of course, students exposure to variables prior to CS comes from algebra. And in algebra, when we say that $x + 3 = 7$, we mean that $x = 4$, and it cannot suddenly become $5$. We can solve for values, but we cannot alter them.
Here's the takeaway: if we, as teachers, don't make explicit how very different it is to be able to change values, a certain percentage of students don't ever fully pick up this idea. They'll get hazy bits and pieces of the idea, but have trouble operating, and ultimately fall behind.
In my experience, they don't appear to get noticeably lost until far later in the year, but by then, it is very hard to get them back on track. (When I take on a new tutee in the months leading up to the AP test, this is one of the first areas I check if they seem generally lost.) I have also come to believe that this is one of the key ideas that most CS teachers miss, and is responsible for a substantial portion of computer science's very bimodal results with students.
There is a real cognitive load to considering not the value of
x, but the value of
x right now, and having to both track that value and figure out when to change it.
In spite of what this all sounds like, I'm not suggesting that functional programming is necessarily easier; it has its own cognitive load, since suddenly we are contemplating many, many simultaneous
x's taking place during recursive calls. It's almost as if learning to talk to something as alien as a computer is always going to be a bit tricky :)