I found recursion rather easy. But I think it's often introduced too early.
Most people I've seen struggling with it hadn't really understood what a function definition was and how they are scoped. Somehow, creating a function and calling it somewhere else didn't totally convey the concept. In most peoples head these two places used a different function somehow, or they didn't understand that a function creates new variables on the stack, they just assumed that they always override the old ones.
