I've taught a few high school courses in the ten years since I graduated college, first in C++ then in Java, and I had always pined for my first language of Pascal. All of these I learned before going through SICP in college, which I didn't properly appreciate.
Last year was my first time teaching introductory programming in a functional language, and I had only 3 students, all clean-slate, virgin programmers. Though sold by the TSRJ workshops, I maintained a healthy level of skepticism. The two items I was most keeping an eye on were "no loops" and "no mutation."
To my great surprise, my students had no issues with structural recursion when sticking to the Design Recipe. It really can come across as a natural way of doing things with proper exposure....
I tell my colleagues that my students do not realize that recursion was supposed to be difficult. I have a similar goal in Algebra I regarding factoring. Unfortunately most of the world wouldn't believe me if I tried to say that such topics actually aren't difficult.
Not only did my students never ask about for/while loops, I never found the need for it. That's part of my elevator pitch, explaining the programs my students made without them. Furthermore, my students never asked about changing a variable value. I feared they would, but it simply didn't come up....