I agree with the author that recursive data structures are a good starting point from which to teach recursion. My favorite example is writing a program that computes the disk space used in a directory, including all of its subdirectories. It's very practical and immediately interesting to students, and they are motivated to understand why it works.

It also helps if students have been exposed to the idea of recursion in math, for example by sequences where a_n is defined in terms of a_{n-1}, and/or proofs by induction.