Sorry for another answer that doesn't fully answer your question, but I have found that the following explanation helps some students so much that they need less practical excercises to understand recursion.
When I explain it as a technique for problem solving I give one riddle as an example, because at least for me and everyone I have talked to this riddle is so complicated to answer that you need to simplify it using recursion.
Maybe you already know it, some people consider it the most difficult riddle there is.
On an island there are 100 people, each with blue eyes. On this island there is the rule that anyone who finds out that they have blue eyes must leave on the next ferry (there's one ferry per day), so each of the 100 inhabitants doesn't know their eye color. Given that they see 99 people with blue eyes everyone must assume that they might be the only one with a different eye color.
Since you don't speak about eye color on that island the situation stays like that.
Now there is a guest on the island, and since he enjoyed his stay he makes a speech when he is about to leave, and as a joke he thought that he gave them a "hint" that contains only information that they already know, so he tells them that there is at least one person with blue eyes on the island.
The riddle is: What happens next?
Now as I said the only way I can argue about an answer is by using recursion, because for recursion you need two things: a trivial case and a way to deduce a more complicated case from the trivial case.
In this riddle the trivial case would be if there was only one person living on the islane. In that case when they were told that there was at least one person with blue eyes it would have to be that one person and they would leave the island on the next ferry.
The way to deduce fron the simple case to a more complex one is to look at the situation with two people on the island, because each of the two persons is observing one person, so each is looking at the trivial case. In the situation with two people there are two possible outcomes: if one of the two has non-blue eyes then the other person is performing the trivial case, because it doesn't matter whether they are the only person on the island or if there are other persons without blue eyes. Persons without blue eyes change the trivial case as much as stones or trees. One of the two persons will see that there is no person with blue eyes in sight and will have to deduce that they are the one person with blue eyes.
But if the second person also has blue eyes the first person will NOT leave the island on the next ferry. That can only mean that they were seeing a person with blue eyes (otherwise they would have had to behave like the trivial case), so when there are two people with blue eyes they both observe that the other one is not leaving on the next ferry and they are both leaving on the second ferry.
Once you have understood that you can extrapolate to 100 people who will have to leave after 100 days when they observe that no one left after 99 days.
It usually takes quite a while until everyone accepts the solution, but I have received good feedback by many students who agreed that it convinced them that there are cases where recursion makes them able to solve a problem that otherwise they couldn't.