Well, I imagine if your background/education wasn't computer science, and you didn't have an intro to algorithms and data structures, (and also not that into math) recursion would feel unnatural and strange.
I say this because I was originally a self-taught programmer, and I hated recursion too. Once I went to school for a CS degree, I learned how awesome it really was, and now I use it all the damn time.
So what is it about recursion that eludes you? It is very strange to me that someone would find one of those concepts easy and the other not -- as you say, they are two forms of the same thing.
I guess it's more reading and writing it in code. In my case, it makes sense to read code like I read a book: it has a beginning, a middle, and an end. (Procedural, see?)
A recursive function makes me do all these convoluted mental gymnastics when I'm just trying to figure out if Cinderella lived happily ever after or not.
I say this because I was originally a self-taught programmer, and I hated recursion too. Once I went to school for a CS degree, I learned how awesome it really was, and now I use it all the damn time.