Interestingly enough, in curriculums that start out with functional languages (e.g. Scheme) students have little trouble with recursion... and then consider iterative loops to be "hard".
Wow, that's surprising, I'd love to hear about some (anecdotal) evidence supporting this.
In college they tried to teach us recursion using C and I didn't get it. Later I discovered The Little Schemer and SICP and it just clicked. It's easier to do in Scheme/Lisp, and those books also explain it better. There's one anecdote. :)