It was counterproductive for me when recursion was taught with Fibonacci and factorials. They were literally the opposite of easy to understand for me, I had absolutely no idea why those examples actually worked, so I just gave up and treated them like magic.

I think recursion should be taught with examples that would be easier for a student to write with recursion than without it. For example, listing all files in a directory.