Could a not-too trivial example like the difference between a Java sudoko solver and a lisp version with all the bells and whistles of FP such as functions as data and return values, recursion and macros be used to illustrate the benefits?
Here's one in Clojure using its core.logic library. I'd say it's pretty neat. You can do something similar in something like Prolog, but a Java implementation would look very different.
