A route into appreciating recursion is to read the following article in Scientific American. Learning recursion in terms of algorithms alone is somewhat limiting. It is more than a fancy way of creating loops, and its application is far-reaching within programming. It might be said that recursion is fundamental to thinking like a human, despite its perceived difficulties in conceptualising the process in computers.
There's an 'inside out' process to recursion, that follows with programming in general. A program is typically a series of mini-puzzles within a puzzle. Many puzzle or adventure games have a primary objective (to win) and secondary objectives in the form of tasks that must be completed in order to continue. An experienced player might be able to devise a strategy to win, having learned and memorised the tactics and consequences of completing each mini-puzzle. A novice player may find completing each mini-game to be enough of a challenge without even considering the consequences.
An experienced programmer will 'see' patterns that novices haven't encountered. It took me a while to speak Spanish with some confidence because the rules were getting in the way of applying them in conversation; I had to let go of the ropes and speak without thinking, and it took quite a few iterations to do so; words became phrases became sentences became paragraphs, with lots of syntactical rules to take into account. Once I had 'modelled' the sentences, I was able to focus on what I wanted to say, not how to say it. I used the feedback of others to refine my ability, and so I was learning Spanish recursively. It is the same process in programming.
The mistake I have repeatedly made in programming and learning in general is thinking someone could teach me. I found those with experience often lacked the viewpoint of beginners, and either over-simplified or over-complicated explanations, usually swinging from one to the other with little warning. I found too many explanations were obfuscated with terminology, similar to grammar clouding my Spanish with terms such as 'participles', 'gerunds' and 'conjunctions'. This type of vocabulary is useful to talk to other programmers or linguists, but it tells you nothing how things work; personal practice and failure tell you these things, along with learning to teach.
Two of my heroes are Claude Shannon and Richard Feynman due to the way they applied learning. In his book, The Pleasure of Finding Things Out, along with his renowned learning technique, Feynman demonstrates that the faculty of learning and teaching are entwined: teach yourself as you mean to teach others, which is a form of recursion.
So, if you want to learn recursion, study it then write about recursion in a way you and anyone else can understand, or study more until that point. What better way to appreciate recursion than to embody it in your way of learning.