People who don't understand recursion have probably never seen a recursive definition in math, or performed an inductive proof. That would be the problem to fix first. Bringing programming into it is just heaping on confusion.

There are recursive structures in nature. Some people might respond to the neatness of recursively generated graphics. Pointing out recursion in language could be useful. Introduce a program for recursively generating random sentences and such.