When I first encountered recursive functions when I began learning programming I had a really hard time understanding what the function would do and how it would play out as it called itself. I couldn't think through the recursion and imagine what would happen. Nor did I really understand how to usefully apply one to a situation. I would either use a loop or a recursive function that utilized lots of external state to work.
When I later encountered functional programming, having learned programming with OOP languages, it was a real mind-bender. I finally started to understand it but when I encountered the need for recursion in FP, it really threw me for a loop. How the hell was I supposed to do this without external state? So it was that restriction that really let me understand how to create a recursive function that could return something useful with nothing more than the initial input. This new understanding also gave me a better appreciation of functional programming and the idea of pure functions.