What are good examples that actually motivate the study of recursion?
I find a very easy to understand example for recursion is the folder structure on a computer.
Look through all folders (within a certain location) and... list all .doc files, for example.

First, you look in the location you were given and see what you're looking for... or not, but you see more folders.
Then you take each of those folders, look into them and see what you're looking for... or not, but you see more folders.
Then you take each of those folders... (you get the idea)

It's a simple function to write and understand (at least in pseudocode, actual implementations may vary^^) and a concept that's easy to grasp for even a complete beginner. Introducing the problem and the manual solution, it's already obvious that each time, the same thing happens again and again. Pseudocode implementation is equally simple to write and grasp:
function findFiles(folder) {
  look for .doc files, if found add them to fileList.txt
  look for folders
  for each found folder: findFiles(foundFolder)
}

I've used this example to explain recursion several times, and never had trouble getting the person to understand it. Even non-programmers can grasp the concept like this.