Analogy for teaching recursion
The Tower of Hanoi was one of the first ways that I encountered recursion.



"The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:


Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
No disk may be placed on top of a smaller disk." (from Wikipedia)


To solve the n disk tower problem:


Solve the n-1 disk tower problem 
Move the nth disk 
Solve the n-1 disk tower problem again.


Solving the 1 disk problem is trivial. 

I can imagine coding this as a nice on-screen or physical computing challenge.