The idea of recursion is not very common in real world. So, it seems a bit confusing to the novice programmers. Though, I guess, they become used to the concept gradually. So, what can be a nice explanation for them to grasp the idea easily?
To explain recursion, I use a combination of different explanation, usually to both try to:


explain the concept,
explain why it matters,
explain how to get it.


For starters, Wolfram|Alpha defines it in more simple terms than Wikipedia:


  An expression such that each term is generated by repeating a particular mathematical operation.




Maths

If your student (or the person you explain too, from now on I'll say student) has at least some mathematical background, they've obviously already encountered recursion by studying series and their notion of recursivity and their recurrence relation.

A very good way to start is then to demonstrate with a series and tell that it's quite simply what recursion is about:


a mathematical function...
... that calls itself to compute a value corresponding to an n-th element...
... and which defines some boundaries.


Usually, you either get a "huh huh, whatev'" at best because they still do not use it, or more likely just a very deep snore.



Coding Examples

For the rest, it's actually a detailed version of what I presented in the Addendum of my answer for the question you pointed to regarding pointers (bad pun).

At this stage, my students usually know how to print something to the screen. Assuming we are using C, they know how to print a single char using write or printf. They also know about control loops.

I usually resort to a few repetitive and simple programming problems until they get it:


the factorial operation,
an alphabet printer,
a reversed alphabet printer,
the exponentation operation.


Factorial

Factorial is a very simple math concept to understand, and the implementation is very close to its mathematical representation. However, they might not get it at first.



Alphabets

The alphabet version is interesting to teach them to think about the ordering of their recursive statements. Like with pointers, they will just throw lines randomly at you. The point is to bring them to the realization that a loop can be inverted by either modifying the conditions OR by just inverting the order of the statements in your function. That's where printing the alphabet helps, as it's something visual for them. Simply have them write a function that will print one character for each call, and calls itself recursively to write the next (or previous) one.

FP fans, skip the fact that printing stuff to the output stream is a side effect for now... Let's not get too annoying on the FP-front. (But if you use a language with list support, feel free to concatenate to a list at each iteration and just print the final result. But usually I start them with C, which is unfortunately not the best for this sort of problems and concepts).

Exponentiation

The exponentiation problem is slightly more difficult (at this stage of learning). Obviously the concept is exactly the same as for a factorial and there is no added complexity... except that you have multiple parameters. And that is usually enough to confuse people and throw them off at the beginning.

Its simple form:



can be expressed like this by recurrence:



Harder

Once these simple problems have been shown AND re-implemented in tutorials, you can give slightly more difficult (but very classic) exercises:


The Fibonacci numbers,
The Greatest Common Divisor,
The 8-Queens problem,
The Towers of Hanoi game,
And if you have a graphical environment (or can provide code stubs for it or for a terminal output or they can manage that already), things like:


Koch's Snow Flake Fractal,
Sierpinski's Triangle.

And for for practical examples, consider writing:


a tree traversal algorithm,
a simple mathematical expression parser,
a minesweeper game.



Note: Again, some of these really aren't any harder... They just approach the problem from exactly the same angle, or a slightly different one. But practice makes perfect.



Helpers

A Reference

Some reading never hurts. Well it will at first, and they'll feel even more lost. It's the sort of thing that grows on you and that sits in the back of your head until one day your realize that you finally get it. And then you think back of these stuff you read. The recursion,  recursion in Computer Science and recurrence relation pages on Wikipedia would do for now.

Level/Depth

Assuming your students do not have much coding experience, provide code stubs. After the first attempts, give them a printing function that can display the recursion level. Printing the numerical value of the level helps.

The Stack-as-Drawers Diagram

Indenting a printed result (or the level's output) helps as well, as it gives another visual representation of what your program is doing, opening and closing stack contexts like drawers, or folders in a file system explorer.

Recursive Acronyms

If your student is already a bit versed into computer culture, they might already use some projects/softwares with names using recursive acronyms. It's been a tradition going around for some time, especially in GNU projects. Some examples include:

Recursive:


GNU - "GNU's Not Unix"
Nagios - "Nagios Ain't Gonna Insist On Sainthood"
PHP - "PHP Hypertext Preprocessor" (and originall "Personal Home Page")
Wine - "Wine Is Not an Emulator"
Zile - "Zile Is Lossy Emacs"


Mutually Recursive:


HURD - "HIRD of Unix-Replacing Daemons" (where HIRD is "HURD of Interfaces representing Depth")


Have them try to come up with their own.

Similarly, there are many occurrences of recursive humor, like Google's recursive search correction. For more information on recursion, read this answer.



Pitfalls and Further Learning

Some issues that people usually struggle with and for which you need to know answers.

Why, oh God Why???

Why would you do that? A good but non-obvious reason is that it is often simpler to express a problem that way. A not-so-good but obvious reason is that it often takes less typing (don't make them feel soooo l33t for just using recursion though...).

Some problems are definitely easier to solve when using a recursive approach. Typically, any problem you can solve using a Divide and Conquer paradigm will fit a multi-branched recursion algorithm.

What's N again??

Why is my n or (whatever your variable's name) different every time? Beginners usually have a problem understanding what a variable and a parameter are, and how to things named n in your program can have different values. So now if this value is in the control loop or recursion, that's even worse! Be nice and do not use the same variable names everywhere, and make it clear that parameters are just variables.

End Conditions

How do I determine my end condition? That's easy, just have them say the steps out loud. For instance for the factorial start from 5, then 4, then ... until 0.

The Devil is in the Details

Do not talk to early abut things like tail call optimization. I know, I know, TCO is nice, but they don't care at first. Give them some time to wrap their heads around the process in a way that works for them. Feel free to shatter their world again later on, but give them a break.

Similarly, don't talk straight from the first lecture about the call stack and its memory consumption and ... well... the stack overflow. I often tutor students privately who show me lectures where they have 50 slides about everything there's to know about recursion when they can barely write a loop correctly at this stage. That's a good example of how a reference will help later but right now just confuses you deeply.

But please, in due time, make it clear that there are reasons to go the iterative or recursive route.

Mutual Recursion

We've seen that functions can be recursive, and even that they can have multiple call points (8-queens, Hanoi, Fibonacci or even an exploration algorithm for a minesweeper). But what about mutually recursive calls? Start with maths here as well. f(x) = g(x) + h(x) where g(x) = f(x) + l(x) and h and l just do stuff.

Starting with just mathematical series makes it easier to write and implement as the contract is clearly defined by the expressions. For instance, the Hofstadter Female and Male Sequences:



However in terms of code, it is to be noted that the implementation of a mutually recursive solution often leads to code duplication and should rather be streamlined into a single recursive form (See Peter Norvig's Solving Every Sudoku Puzzle.
